combinations of N same balls in A different boxes

Question

int f(int n,int a,int x)
{
        if(a==1)
        {
            if(n>=0 && n<=x)  //HERE WAS ERROR,sorry
                return 1;
            else 
                return 0;
        }

        int ans=0;

        for(int i=0;i<=x;i++)
            ans += f(n-i,a-1,x);

    return ans;
}

Hello! enter image description here

Example:

Here is algorithm, but it spends very much time. Maybe you know a faster way to solve this problem? Thanks very much and sorry for worry.

@leppie: since the OP calls it an *algorithm*, it must be pseudocode ;) — Fred Foo, Nov 10 '11 at 11:18
@leppie I don't think it matters too much - it's the algorithm that is important. — Oliver, Nov 10 '11 at 11:20
@LuVue: if the answer to your example is 1, then why does your function return 9? Oh and the answer is dynamic programming. — Fred Foo, Nov 10 '11 at 11:20
@leppie: It does not matter, I just want to know the algorithm ... — Lu Vue, Nov 10 '11 at 11:21
If you had n=3, a=2,x=2, is the answer 2 or 1? That is, does it matter which box the balls are in? — Oliver, Nov 10 '11 at 11:26
@larsmans: Sorry, in that code was a mistake. I corrected it in my question. — Lu Vue, Nov 10 '11 at 11:27
@Oliver: Answer is 2, becouse: 1)first box-1 ball, second box-2 balls; 2)first box-2 balls, second box-1 ball — Lu Vue, Nov 10 '11 at 11:31
Amazing how pseudocode has evolved as a language over the years. Back in the day it used to look like Pascal that wouldn't compile, now it's C that doesn't compile ;) — SmacL, Nov 10 '11 at 11:44

Wisdom's Wind · Accepted Answer · 2011-11-10T12:16:14.307

What you need is dynamic programming. You need to memorize values of function f for those arguments for which it already have been calculated. Also it can be implemented without recursion like this:

int f(int n,int a,int x)
{
    int q[1000][50]; // to simplify and not use dynamic allocation assume that a < 50 and n < 1000

    q[0][0] = 1;
    for (int i = 1; i < 1000; ++i)
        q[i][0] = 0;

    for (int i = 1; i <= a; ++i)
    {
        for (int j = 0; j <= n; j++)
        {
            int t = 0;
            for (int l = 0; l <= j && l <= x; ++l)
                t += q[j - l][i-1];
            q[j][i] = t;
        }
    }

    return q[n][a];
}

This is only simple technique demonstration. It can be optimized one more time, you can precalculate t-sum and eliminate loop for l. And you don't have to store whole table q, you only need two layers, it will reduce memory usage. So the result will look like this:

int f(int n,int a,int x)
{
    int q[1000][2]; // to simplify and not use dynamic allocation assume n < 1000

    q[0][0] = 1;
    for (int i = 1; i < 1000; ++i)
        q[i][0] = 0;

    int current = 1;
    for (int i = 1; i <= a; ++i)
    {
        int t = 0;
        for (int j = 0; j <= n; j++)
        {
            t += q[j][1 - current];
            if (j > x)
                t -= q[j - x - 1][1 - current];

            q[j][current] = t;
        }
        current = 1 - current;
    }

    return q[n][1 - current];
}

So finally it will take O(a*n) time to compute.

PS: Note that answer can be a huge number which can overflow any native integer type.

Agree. But it will make code bit more complicated. I guess 2*n variant it's enough for technique explanation. If you can add understandable sample with x+1 memorization, you are welcome. — Wisdom's Wind, Nov 10 '11 at 12:22

score 2 · Answer 2 · answered Nov 10 '11 at 11:58

First of all, if A*X < N, there's no way to distribute the balls, so you can stop earlier. If A*X == N, there's only one way. Then it's probably faster to first pick the number of boxes in which you place X balls and recur with a smaller limit.

int f(int n, int a, int x){   // should all be unsigned, actually
    if (n == 0){
        return 1;
    }
    int p = a*x;
    if (p < n){
        return 0;
    }
    if (p == n){
        return 1;
    }
    if (x == 1){
        return binom(a,n);    // ways to choose n boxes from a boxes
    }
    // now the interesting cases
    int ways = 0;    // should perhaps be unsigned long long, that number grows fast
    int xCount, tempRes, min, max;
    min = a+n-p;
    if (min < 0) min = 0;
    max = n/x;
    for(xCount = min; xCount <= max; ++xCount){
        tempRes = f(n - x*xCount,a - xCount, x-1); // ways to distribute the remaining balls
        ways += binom(a,xCount)*tempRes;    // multiply by the number of ways to choose xCount boxes
    }
    return ways;
}

It might be useful to create a table for the binomial coefficients if you call f often.

score 2 · Answer 3 · answered Nov 10 '11 at 14:05

2

look at http://www.mathpages.com/home/kmath337.htm and the formula at the bottom of the page.

answered Nov 10 '11 at 14:05

John Donn

1,718
2
19
45

You mean C[m+k-s(t,j)-1,m-1] ? – Lu Vue Nov 10 '11 at 15:53
At the bottom you find the formula for N(k) which is an alternating sum of m terms, where m should be the number of the boxes (each term is a product of certain binomial coefficients). – John Donn Nov 10 '11 at 16:16
John Donn, I did not understand this :( – Lu Vue Nov 10 '11 at 16:29
2

@LuVue There's only one formula at the bottom. It's in plain text so it might be hard to read. [This](https://chart.googleapis.com/chart?cht=tx&chl=N%28k%29+%3D+%5Csum_%7Bt%3D0%7D%5Em+%28-1%29%5Et+%7Bm+%5Cchoose+t%7D+%7B%7Bm%2Bk-t%28R%2B1%29-1%7D+%5Cchoose+%7Bm-1%7D%7D) might help. – ladaghini Nov 10 '11 at 17:31

combinations of N same balls in A different boxes

3 Answers3