Generating all permutations of N balls in M bins

Question

I want to generate a set of permutations of n balls in m bins. The following set of nested lists generates those permutations.

n <- 3
m <- 4
v <- rep(0,m)
for (i in n:0){
  for (j in (n-sum(i)):0){
    for (k in (n-sum(i,j)):0){
      for (l in (n - sum(i,j,k)):0){
        v <- c(i,j,k,l)
        print(v)
        if (sum(v) == n){ break }
      }
    }
  }
}

Which prints the solution:

[1] 3 0 0 0
[1] 2 1 0 0
[1] 2 0 1 0
[1] 2 0 0 1
[1] 1 2 0 0
[1] 1 1 1 0
[1] 1 1 0 1
[1] 1 0 2 0
[1] 1 0 1 1
[1] 1 0 0 2
[1] 0 3 0 0
[1] 0 2 1 0
[1] 0 2 0 1
[1] 0 1 2 0
[1] 0 1 1 1
[1] 0 1 0 2
[1] 0 0 3 0
[1] 0 0 2 1
[1] 0 0 1 2
[1] 0 0 0 3

The total number of permutations will be choose(n+m-1,m-1), and the order of the permutations does not matter to me. But I am having a hard time making this into a function that can take an arbitrary number of bins. (I won't spoil the well with my attempts, it is just jumble of nested loops though.) So if someone more saavy than me could translate the nested loops above into a function I would appreciate it.

Or if there is already a function available to conduct this type of permutation (or a different algorithm to follow) I would appreciate being told about it. I would prefer an approach that does not generate superfluous permutations (here ones that do not add up to n) and then discards them, but for small problems like this a solution that does that would be acceptable.

Answer 1

Using the excellent RccpAlgos package. From 2.6.0 there are several integer composition functions.

compositionsGeneral(v = 0:3, m = 4, repetition = TRUE, weak = TRUE)

      [,1] [,2] [,3] [,4]
 [1,]    0    0    0    3
 [2,]    0    0    3    0
 [3,]    0    3    0    0
 [4,]    3    0    0    0
 [5,]    0    0    1    2
 [6,]    0    0    2    1
 [7,]    0    1    0    2
 [8,]    0    1    2    0
 [9,]    0    2    0    1
[10,]    0    2    1    0
[11,]    1    0    0    2
[12,]    1    0    2    0
[13,]    1    2    0    0
[14,]    2    0    0    1
[15,]    2    0    1    0
[16,]    2    1    0    0
[17,]    0    1    1    1
[18,]    1    0    1    1
[19,]    1    1    0    1
[20,]    1    1    1    0

---

Pre-RcppAlgos 2.6.0 alternative

Answer 2

Here is a base R solution that returns a list.

get_list <- function(M, N) {
  # All permutations
  perms <- expand.grid(rep(list(0:N), M))
  
  # Keep those meeting constraints
  kept <- perms[rowSums(perms) == N,]
  
  # Return as list
  if (length(kept) > 1) {
    split(kept, seq(nrow(kept)))
  } else {
    as.list(kept)
  }
  
}

# Compute
get_list(N = 5, M = 1)
#> [[1]]
#> [1] 5
get_list(N = 2, M = 3)
#> $`1`
#>   Var1 Var2 Var3
#> 3    2    0    0
#> 
#> $`2`
#>   Var1 Var2 Var3
#> 5    1    1    0
#> 
#> $`3`
#>   Var1 Var2 Var3
#> 7    0    2    0
#> 
#> $`4`
#>    Var1 Var2 Var3
#> 11    1    0    1
#> 
#> $`5`
#>    Var1 Var2 Var3
#> 13    0    1    1
#> 
#> $`6`
#>    Var1 Var2 Var3
#> 19    0    0    2

Answer 3

This can be done pretty easily in R - I see a lot of complicated algorithms out there, but it can be done by shifting bars. We keep track of the locations of partitions (bars) rather than how many are in each bin. If there are 3 objects that makes 3 bar positions:

objects         O O O 
bar position   0 1 2 3 

For example, if we have N=3 and K=4 bins, we will have K-1=3 bars. Begin with all bars position 0

|||OOO

In other words, all objects are in bin 4. The algorithm goes like this:

1. Find the right-most bar that is not in position N. Increment that bar position by 1, and also collect all bars to the right to that position.
2. Record the partition
3. Go to 1: Repeat until all bars are in position N

This will iterate through every partitioning of N objects into K bins.

1. |||OOO starting permutation; bump bar 3
2. ||O|OO bar 3 is in position 1; bump it
3. ||OO|O bar 3 is in position 2; bump it
4. ||OOO| bar 3 is in position 3. bar 2 is in position 0; bump it and reset bar 3
5. |O||OO bar 3 is in position 1; bump it
6. |O|O|O bar 3 is in position 2; bump it
7. |O|OO| bar 3 is in position 3. bar 2 is in position 1; bump it and reset bar 3
8. |OO||O

and so on.

N=3
K=4
k=K-1
bars=rep(0,k)
bars[k]=-1      #so bars should be a vector of k-1 0s and then a -1; 


while(bars[1]<N){    #if the first bar is at position N then we're done
  for(j in k:1){     #go backwards through bars
    if(bars[j]<N){   #the first bar that is not in the final position...
      bars[j:k]=bars[j]+1 ##bump it up by 1 and reset all subsequent bars
      break
    }
  }
  print(c(bars,N)-c(0,bars))  
  ##this just translates bar positions into bin counts
}

Answer 4

The following gives a slightly different but equivalent answer by using a more general package iterpc

m = 4; n = 3
library(iterpc)
I = iterpc(m, n, replace=T)
getall(I)

The output is the bin numbers for the n balls.

     [,1] [,2] [,3]
 [1,]    1    1    1
 [2,]    1    1    2
....
....
[18,]    3    3    4
[19,]    3    4    4
[20,]    4    4    4

The first line means that the 3 balls are all from bin 1 while the last line means that the 3 balls are all from bin 4.

You can easily produce your desired result by counting numbers of 1, 2, 3 and 4's. And you can also make use of the iterator to generate the result sequentially.

count <- function(x){
    as.numeric(table(factor(x, levels=1:m)))
}
I = iterpc(m, n, replace=T)


> count(getnext(I))
[1] 3 0 0 0
> count(getnext(I))
[1] 2 1 0 0
> count(getnext(I))
[1] 2 0 1 0
> count(getnext(I))
[1] 2 0 0 1

Answer 5

library(partitions)
compositions(3,4)

# [1,] 3 2 1 0 2 1 0 1 0 0 2 1 0 1 0 0 1 0 0 0
# [2,] 0 1 2 3 0 1 2 0 1 0 0 1 2 0 1 0 0 1 0 0
# [3,] 0 0 0 0 1 1 1 2 2 3 0 0 0 1 1 2 0 0 1 0
# [4,] 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 3