找到将元素列表拆分为相同大小的给定数量的组的所有可能方法

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号.我想要一个列出所有可能的方法,将这些个体分成所需数量的组,这些组都具有相同的大小.

如果我没有弄错的话,目前唯一可行的解​​决办法就是朱巴所谓的暴力和肮脏的解决方案.但正如朱巴所说,它很快(为了我的目的太快了!)无法使用.

再次感谢

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