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