Results 1 to 5 of 5

Math Help - Looking for algorithm to generate occupancy numbers of n balls into k cells

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    18

    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

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    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);
            }
            return total;
        }
    }
    
    
    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);
    }
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2008
    Posts
    18
    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!
    Last edited by cduston; May 7th 2009 at 07:27 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by cduston View Post
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 7th 2011, 04:58 PM
  2. calculating grid cells in move between cells
    Posted in the Algebra Forum
    Replies: 15
    Last Post: January 21st 2011, 11:38 AM
  3. a basket contains 5 red balls, 3 blue balls, 1 green balls
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: May 28th 2010, 02:39 AM
  4. Occupancy Models: Please spot the flaws!
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: November 16th 2007, 02:21 PM
  5. Numbers of balls in a frustum
    Posted in the Geometry Forum
    Replies: 2
    Last Post: September 10th 2006, 08:56 AM

Search Tags


/mathhelpforum @mathhelpforum