# Thread: Looking for algorithm to generate occupancy numbers of n balls into k cells

1. ## Looking for algorithm to generate occupancy numbers of n balls into k cells

Hey everyone,
So I need an algorithm that will generate all the occupancy numbers for n (indistinguishable) balls into k (distinguishable) cells, where you are allowed to have empty cells. I know the total number of such ways to do so is

$\displaystyle C(k+n-1,n)=\binom{k+n-1}{n}$

But for a code I am writing I need to be able to generate all of them. Unfortunately, since I will be doing this for fairly large numbers (16 balls in 3-10 cells, so we're talking 10^2 - 10^9 possibilities), I don't want to include a routine to check each permutation, I want to just generate them straight away.

In case anyone isn't following, say I want to put 3 balls into 3 cells. Then the possible ways of doing this are
3 0 0
2 1 0
2 0 1
0 3 0
1 2 0
0 2 1
0 0 3
1 0 2
0 1 2
1 1 1

ie There are 10. But I need to throw this in a code; anyone know an easy way to do this for general n and k?

Thanks!

2. I think that you need to find a really good programmer.
I don’t this is a mathematical problem.
The best we can give is to tell the number of ways to partition integers into a certain number of summands.
For example 16 can be partitioned into 10 or fewer summands in 212 ways.
Example: 16=1+1+2+3+4+5 that is with six summands.
But that does help list the different occupancy configurations

3. Hi,

I think a slightly mathematically enclined casual programmer is enough. And I think that algorithmics is indeed maths (and informatics), even though there certainly are forums that are more relevant for such questions.

About your problem. How would you procede "by hand"? Put a few balls in the first box (any number from 0 to n), then (among the remaining ones) put a few balls in the second ones, etc., until the last box where you put all the remaining balls.

If you have 4 boxes, you can do this with three nested "for" loops:
Code:
for i_1=0 to n
for i_2=n-i_1 to n
for i_3=n-i_1-i_2 to n
a solution is : i_1, i_2, i_3, n-i_1-i_2-i_3
end_for
end_for
end_for
"Fine, you say, but what if I don't know k? How can I have my program do k-1 for-loops?".

Answer (a classical one): to overcome this problem, use a recursive function. The idea is that you make a function that calls itself, according to the following scheme :
Code:
function balls_in_boxes(n,k)
if k=1,
put the n balls in the only box
else,
for i=0 to n,
use balls_in_boxes(n-i,k-1)  (it allows to put n-i balls in k-1 boxes)
and put i balls in the last box
end_for
end_if
end_function
To make this more precise, you need the function to return the list of possible solutions. Depending on the programming language, this can be done in various ways.

Here is a working program in C language that I just wrote. It writes the solutions on the screen. You'll have to make a few changes if you want to store the configurations. In my function, I chose to give as an argument the positions of the balls that have been put before, so I can print them at the end. I put comments in the code.

Code:
#include <stdio.h>
#include <stdlib.h>

// Lists on the screen the different Ways to put n balls in k(>=1) boxes (empty boxes allowed), followed by the "nb" numbers given by the array "start" (useful for recursion) ; returns the number of solutions
// So if we only want the ways to put n balls in k boxes, we choose nb=0 and "start" is any pointer (for instance, the NULL pointer will do fine)
int balls_in_boxes(int n,int k,int *start,int nb)
{
int i,j,total;
int *start2;

if(k==1)
{
// Just print the given starting numbers and put the balls in the only box
i=0;
while(i<nb)
{
printf("%d ",start[i]);
i++;
}
printf("%d\n", n);
return 1;
}
else
{
// Choose the number i (0<=i<=n) of balls to put in the first box, and call the function on the next k-1 boxes for n-i balls.
total=0;
for(i=0;i<=n;i++)
{
// Make an array of size nb+1 to store the position of balls
start2=malloc((nb+1)*sizeof(int));
// Copy "start" into the first nb cells of "start2"
for(j=0;j<nb;j++)
start2[j]=start[j];
// Add a new cell with i balls
start2[nb]=i;
total += balls_in_boxes(n-i,k-1,start2,nb+1); // Print what we want, and count
free(start2);
}
}
}

int main(void)
{
int n,k,total;

n=3; k=3;

total=balls_in_boxes(n,k,NULL,0);
printf("\nNumber of solutions : %d\n",total);

exit(0);
}

4. I am sorry if people don't feel this is an appropriate place to post this question, but I categorize studying algorithms as part of descrete math...I was not actually expecting anyone to provide me with specific code. But since someone did...

Great, thanks Laurent! My programming knowledge is pretty thin, so I might not have thought of just making a recursive function. In any case, it sounds like a fine solution for my problem. Thanks a bunch!

EDIT: Laurent, I've checked your algorithm (by hand, not coding it) and I don't think it works. Basically, since you are starting with i_1=0 to n and i_2=n-i_1 to n, all the balls go into the first two cells. In other words, when I check your algorithm I get (for n=4)
0 4 0 0
1 3 0 0
2 2 0 0
3 1 0 0
4 0 0 0

I think you need to count upwards for each i, like 0 0 0 4, 0 0 1 3, 0 0 2 2 etc. In any case, the concept of the recursive function is probably good enough to get me going, which means I should have posted this in a coding forum anyway :-P

Thanks all!

5. Originally Posted by cduston
EDIT: Laurent, I've checked your algorithm (by hand, not coding it) and I don't think it works. Basically, since you are starting with i_1=0 to n and i_2=n-i_1 to n, all the balls go into the first two cells. In other words, when I check your algorithm I get (for n=4)
0 4 0 0
1 3 0 0
2 2 0 0
3 1 0 0
4 0 0 0
Yes indeed, it should have been "for i_2=0 to n-i_1" and the same for the others, I wrote this too quickly. In fact my point was that this method was not the good one, and I took greater care of the recursive algorithm, which works fine (the code runs well).