#### Log in

No account? Create an account

## 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?

## Comments

( 5 comments — Leave a comment )

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? 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;
}
}
``` 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. 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 )

### Profile Grieve

### Latest Month

S M T W T F S July 2011 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

### Page Summary

Powered by LiveJournal.com 