6

我有一个元素列表，我想要一个对象，它可以为我提供将这些元素拆分为给定数量的相同大小的组的所有可能方法。

例如，这是我的清单：

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 的所谓的 brute-force-and-dirty 解决方案。但正如朱巴所说，它很快（对我的目的来说太快了！）无法使用。

再次感谢

4

3 回答 3

5

遵循递归逻辑允许您计算所有组合而无需重复，也无需先计算所有组合。只要 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
于 2013-02-07T18:11:49.367 回答
1

这里有一个基于分离柱构造的解决方案。

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
于 2013-02-07T15:41:55.227 回答
0

这是一个蛮力和肮脏的解决方案，它可能适用于不同数量的组，但您确实应该在使用前对其进行测试。此外，当它使用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
于 2013-02-07T14:54:13.293 回答