Generating all permutations of N balls in M bins

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.

Solution 1:

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

Solution 2:

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