Enumerate all possible distributions of n balls into k boxes

Question

The exact problem i am referring to and the number of distributions for the problem is computed here. I am interested in knowing those distributions explicitly.

For example, there are 5 balls and 3 boxes: one distribution is 2 balls in box 1, 2 in box 2, 1 in box 3 referred to as, say 221. Now i want to list all such possible distributions: -

212

131

104

. . .

One way is that i run the matlab command: perms([0,0,0,0,0,1,1,1]). This essentially generates all permutations of 5 balls and 2 sticks. but there is massive over-counting as the command perms does not recognize identical objects.

score 0 · Answer 1 · answered Nov 17 '17 at 22:39

0

You can use unique() to get rid of identical rows generated by perms():

A = unique(perms([0,0,0,0,0,1,1,1]), 'rows');
% `A` will contain all combinations, not permutations, of [0,0,0,0,0,1,1,1]

answered Nov 17 '17 at 22:39

frslm

2,969
3
13
26

score 0 · Accepted Answer · answered Nov 17 '17 at 22:42

Very simple ... sort of.

function alloc(balls, boxes):

    if boxes = 1
        return [balls]
    else
       for n in range 0:balls
           return alloc(balls-n, boxes-1)

That's the basic recursion logic: pick each possible quantity of balls, then recur on the remaining balls and one box fewer.

The list-gluing methods will be language-dependent; I leave them as an exercise for the student.

Enumerate all possible distributions of n balls into k boxes

2 Answers2