Find all possible ways to split a list of elements into a a given number of group of the same size

Question

I have a list of elements and I want an object that gives me all possible ways of splitting these elements into a given number of groups of the same size.

For example here is my list:

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

And I want all possible combinations of spliting them into 2 groups:

nb.groups <- 2

The answer might for example be of that kind:

[[1]]

[1] 1,2

[2] 3,4

[[2]]

[1] 1,3

[2] 2,4

[[3]]

[1] 2,3

[2] 1,4

I want to avoid the repetition of that kind:

[[1]]

[1] 1,2

[2] 3,4

[[2]]

[1] 3,4

[2] 1,2

Thanks a lot !

Thank you for answering. I think I should give you more informations about what I'm trying to achieve.

the list (or vector because obviously MyElements was a vector) is actually ID numbers for individuals. I want a list of all possible ways of splitting these individuals in a desired number of groups which all have the same size.

If I'm not mistaken the only solution which actually works for the moment is the so-called brute-force-and-dirty solution from Juba. But as Juba said, it gets quickly (way too quickly for my purposes !) unusable.

Thanks again

Answer 1

Following recursive logic allows you to calculate all combinations without repetitions and without the need to calculate all of them first. It works pretty nice, as long as choose(nx-1,ning-1) returns an integer. If it doesn't, calculating the possibilities is a bit ridiculous.

It's a recursive process, so it might take long and it will cause memory trouble when your vectors exceed a certain limit. But then again, dividing a set of 14 elements in 7 groups gives already 135135 unique possibilities. Things get out of hand pretty quick in these kind of things.

The logic in pseudo-something (wouldn't call it pseudocode)

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

Translating this to R gives us :

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    
}

To show it works :

> 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

Answer 2

here a solution based on the construction of splitter column.

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

Answer 3

Here is a brute-force-and-dirty solution, which may work for different number of groups, but you really should test it before use. Moreover, as it uses permn, it will be unusable very fast depending on the size of your vector :

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)
}

Which gives, for example :

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

Or :

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