将一个元素列表分成给定数量的相同大小的组的所有可能方法

Question

我有一个元素列表，我想要一个对象，它可以将这些元素分成指定数量相同大小的组，并给出所有可能的分组方式。

例如，这是我的列表：

MyElements <- c(1,2,3,4)

我想要将它们划分为两组的所有可能组合：

nb.groups <- 2

答案可能是那种类型的，例如：

[[1]]

[1] 1,2

[2] 3,4

[[2]]

[1] 1,3

[2] 2,4

[[3]]

[1] 2,3

[2] 1,4

我想避免那种重复。

[[1]]

[1] 1,2

[2] 3,4

[[2]]

[1] 3,4

[2] 1,2

非常感谢！

谢谢你的回答。我想我应该给你更多关于我想要实现的内容的信息。

这个列表（或向量，因为MyElements显然是一个向量）实际上是个人的ID号码。我想要一个将这些个体分成所需数量且大小相同的组的所有可能方式的列表。

如果我没有错的话，目前唯一可行的解决方案是Juba提出的所谓的暴力和肮脏的解决方案。但正如Juba所说，它很快就会变得不可用（对我的目的来说太快了！）。

再次感谢。

- Remi.b

---

你的“list”实际上是一个vector。 - Roland

(1,2,3,4) 和 (1,2,4,3) 是可取的吗？ - Arun

最近似乎经常出现排列和组合之间的混淆。看起来你想要的是组合，而不是排列，在这种情况下，我认为Juba的答案是合适的。 - Carl Witthoft

@CarlWitthoft也许我的回答是合适的，但从计算的角度来看几乎是不可用的。肯定有更好、更优雅的算法。 - juba

Answer 1

以下递归逻辑可让您计算所有组合，无需重复计算并且无需先计算所有组合。只要choose(nx-1,ning-1)返回一个整数，它就能很好地工作。如果没有返回整数，则计算可能性有点荒谬。

这是一个递归过程，所以当您的向量超过一定限制时，它可能需要很长时间并引起内存问题。但是，将14个元素的集合分成7组已经产生了135135个独特的可能性。在这种情况下，事情会很快失控。

伪代码中的逻辑（不称之为伪代码）。

nb = number of groups
ning = number of elements in every group
if(nb == 2)
   1. take first element, and add it to every possible 
       combination of ning-1 elements of x[-1] 
   2. make the difference for each group defined in step 1 and x 
       to get the related second group
   3. combine the groups from step 2 with the related groups from step 1

if(nb > 2)
   1. take first element, and add it to every possible 
       combination of ning-1 elements of x[-1] 
   2. to define the other groups belonging to the first groups obtained like this, 
       apply the algorithm on the other elements of x, but for nb-1 groups
   3. combine all possible other groups from step 2 
       with the related first groups from step 1

将其翻译成 R 语言：

perm.groups <- function(x,n){
    nx <- length(x)
    ning <- nx/n

    group1 <- 
      rbind(
        matrix(rep(x[1],choose(nx-1,ning-1)),nrow=1),
        combn(x[-1],ning-1)
      )
    ng <- ncol(group1)

    if(n > 2){
      out <- vector('list',ng)

      for(i in seq_len(ng)){
        other <- perm.groups(setdiff(x,group1[,i]),n=n-1)
        out[[i]] <- lapply(seq_along(other),
                       function(j) cbind(group1[,i],other[[j]])
                    )
      }
    out <- unlist(out,recursive=FALSE)
    } else {
      other <- lapply(seq_len(ng),function(i) 
                  matrix(setdiff(x,group1[,i]),ncol=1)
                )
      out <- lapply(seq_len(ng),
                    function(i) cbind(group1[,i],other[[i]])
              )
    }
    out    
}

展示它的工作原理：

> perm.groups(1:6,3)
[[1]]
     [,1] [,2] [,3]
[1,]    1    3    5
[2,]    2    4    6

[[2]]
     [,1] [,2] [,3]
[1,]    1    3    4
[2,]    2    5    6

[[3]]
     [,1] [,2] [,3]
[1,]    1    3    4
[2,]    2    6    5

[[4]]
     [,1] [,2] [,3]
[1,]    1    2    5
[2,]    3    4    6

[[5]]
     [,1] [,2] [,3]
[1,]    1    2    4
[2,]    3    5    6

[[6]]
     [,1] [,2] [,3]
[1,]    1    2    4
[2,]    3    6    5

[[7]]
     [,1] [,2] [,3]
[1,]    1    2    5
[2,]    4    3    6

[[8]]
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    4    5    6

[[9]]
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    4    6    5

[[10]]
     [,1] [,2] [,3]
[1,]    1    2    4
[2,]    5    3    6

[[11]]
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    5    4    6

[[12]]
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    5    6    4

[[13]]
     [,1] [,2] [,3]
[1,]    1    2    4
[2,]    6    3    5

[[14]]
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    6    4    5

[[15]]
     [,1] [,2] [,3]
[1,]    1    2    3
[2,]    6    5    4

- Joris Meys

---

太棒了！它似乎完美地运行了！我花了整整一天的时间都没有成功！谢谢你们，也感谢所有亲爱的stackoverflow读者！ - Remi.b

不客气。你知道你可以通过点击帖子左侧的V符号来接受正确答案吗？ - Joris Meys

你在不到10分钟的时间里教会了我两件事情 ;) - Remi.b

Answer 2

基于分隔列构建的解决方案如下。

x <- 1:4
a <- as.data.frame(t(combn(x,length(x)/2))
a$sum <- abs(rowSums(a)-mean(rowSums(a)))
lapply(split(a,a$sum),function(x) if(dim(x)[1]>2) 
                                      split(x,1:(dim(x)[1]/2)) 
                                   else 
                                      x)



$`0`
  V1 V2 sum
3  1  4   0
4  2  3   0

$`1`
  V1 V2 sum
2  1  3   1
5  2  4   1

$`2`
  V1 V2 sum
1  1  2   2
6  3  4   2

- agstudy

---

我认为这不是原帖所询问的内容。 - Arun

我认为OP并不希望重复。例如，在1中，如果是1,2，那么另一个可以是3,4或4,3，但不能是2,3，因为2已经被“分配”了。至少这是我理解的方式。 - Arun

Answer 3

这里有一个粗暴而不太优雅的解决方案，可以适用于不同数量的组，但在使用之前确实应该进行测试。此外，由于它使用了permn，所以根据您的向量大小，它将非常快速地变得无法使用：

library(combinat)
split.groups <- function(x, nb.groups) {
  length.groups <- length(x)/nb.groups
  perm <- permn(x)
  perm <- lapply(perm, function(v) {
    m <- as.data.frame(matrix(v, length.groups, nb.groups))
    m <- apply(m,2,sort)
    m <- t(m)
    m <- m[order(m[,1]),]
    rownames(m) <- NULL
    m})
  unique(perm)
}

例如，这将会给出：

R> split.groups(1:4, 2)
[[1]]
     [,1] [,2]
[1,]    1    2
[2,]    3    4

[[2]]
     [,1] [,2]
[1,]    1    4
[2,]    2    3

[[3]]
     [,1] [,2]
[1,]    1    3
[2,]    2    4

或者：

R> split.groups(1:6, 3)
[[1]]
     [,1] [,2]
[1,]    1    2
[2,]    3    4
[3,]    5    6

[[2]]
     [,1] [,2]
[1,]    1    2
[2,]    3    6
[3,]    4    5

[[3]]
     [,1] [,2]
[1,]    1    6
[2,]    2    3
[3,]    4    5

[[4]]
     [,1] [,2]
[1,]    1    2
[2,]    3    5
[3,]    4    6

[[5]]
     [,1] [,2]
[1,]    1    6
[2,]    2    5
[3,]    3    4

[[6]]
     [,1] [,2]
[1,]    1    5
[2,]    2    6
[3,]    3    4

[[7]]
     [,1] [,2]
[1,]    1    5
[2,]    2    3
[3,]    4    6

[[8]]
     [,1] [,2]
[1,]    1    5
[2,]    2    4
[3,]    3    6

[[9]]
     [,1] [,2]
[1,]    1    6
[2,]    2    4
[3,]    3    5

[[10]]
     [,1] [,2]
[1,]    1    4
[2,]    2    3
[3,]    5    6

[[11]]
     [,1] [,2]
[1,]    1    4
[2,]    2    6
[3,]    3    5

[[12]]
     [,1] [,2]
[1,]    1    4
[2,]    2    5
[3,]    3    6

[[13]]
     [,1] [,2]
[1,]    1    3
[2,]    2    5
[3,]    4    6

[[14]]
     [,1] [,2]
[1,]    1    3
[2,]    2    6
[3,]    4    5

[[15]]
     [,1] [,2]
[1,]    1    3
[2,]    2    4
[3,]    5    6

- juba

---

你为什么在那里加入了 as.data.frame？ - Roland

@Roland 为了能够独立地对每一列进行排序。我告诉过你这很麻烦 :) - juba