?

Log in

No account? Create an account

Previous Entry | Next Entry

Math puzzle

I ran across this problem today, and I feel like it must have been solved before, but I am not sure where to look. Suppose you have X objects and Y buckets. The question is how many unique ways can I distribute the X objects into the Y buckets.

For example if I have 2 objects and 3 buckets I can distribute the two objects as follows:
2 0 0
0 2 0
0 0 2
1 1 0
1 0 1
0 1 1

Which gives me six unique ways to distribute the objects.

With 3 objects and 3 buckets there are 10 ways to do it. My question is what is the algorithm given X and Y which will give you all unique combinations?

Tags:

Comments

( 5 comments — Leave a comment )
kevin_hogan
Nov. 9th, 2007 04:20 am (UTC)
If you let (m,n) be how many ways you can distribute m things among n buckets, then work inductively from:

(n,1) = (0,n) = 1

to get (m,n) = C((n-1)+m,m) = ((n-1)+m)!/[m!(n-1)!]

It does have an oddly deja-vu feel to it, doesn't it?
grieve
Nov. 9th, 2007 06:56 am (UTC)
That looks right, but what I am really looking for is not the algorithm to give me the total number for (m,n), but the actual list of unique distributions of (m,n). I should have stated that more clearly in the original post.

Thanks for posting though I can use your algorithm to verify the other algorithm if I figure it out. :)
(Anonymous)
Nov. 9th, 2007 05:08 pm (UTC)
Well then - that's much easier, since you're going to have to do all the work anyway... Here's a recursive solution - it strikes me as a bit tail-recursive, so you could probably iterate this with less stack usage...

void print_distribution(int things, int buckets) {
   int* bucket_space;
   if ((things < 0)||(buckets < 1)) {
       cout << "impossible!" << endl;
   }
   else {
          if (bucket_space = (int*)alloca(buckets*sizeof(int)))
             print_sub_distribution(bucket_space, buckets, 1, things);
          else
             cout << "out of memory" << endl;
       }
}

void print_sub_distribution(int* bucket_space, int n_buckets, int current_bucket, int things_left) {
    int i;
    if (current_bucket == n_buckets) {
       bucket_space[current_bucket-1] = things_left;
       cout << "[ ";
       for (i=0; i < n_buckets; i++) {
           cout << i << " ";
       }
       cout << "]" << endl;
    }
    else if (current_bucket < n_buckets) {
       for (i=0; i<=things_left) {
          bucket_space[current_bucket-1] = i;
          print_sub_distribution(bucket_space, n_buckets, current_bucket+1, things_left - i);
       }
    }
    else {
       cout << "bad argument to print_sub_distribution" << endl;
    }
}
grieve
Nov. 12th, 2007 04:05 am (UTC)
Cool. I ran a test, and it seems to almost work. At some point it went into an endless loop. I think it is probably just a minor error in the base condition, but I didn't really get a lot of time to look into it. Maybe later this week I will.
grieve
Nov. 12th, 2007 09:11 pm (UTC)
Turns out there was no infinite loop, just a printing problem. I just too impatient to see that it would end.
for (i=0; i < n_buckets; i++) {
           cout << i << " ";
       }

Needs to change to
for (i=0; i < n_buckets; i++) {
           cout << bucket_space[i] << " ";
       }

and
for (i=0; i<=things_left)

needs to change to
for (i=0; i<=things_left; ++i)
( 5 comments — Leave a comment )

Latest Month

July 2011
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31      

Page Summary

Powered by LiveJournal.com
Designed by yoksel