Given n identical balls and m unique bins, where each bin has a certain capacity (from 0 to z, where z is a non-negative integer less than or equal to 15), how many different ways are there of distributing the balls? Is there a general purpose algorithm for solving this type of problem?
I have come across the "stars and bars" and "inclusion/exclusion" principle but I have also found some questions/answers here on stackoverflow, but none of the answers seem general enough to be extendable to arbitrary sizes of n. It seems that one way of solving it is with dynamic programming. How can this be done, for arbitrary n (the problem with the solution below is the recursion depth becomes too large in Python for relatively small n, such as n = 1000).
Rank and unrank combinations to distribute k balls into n bins of different capacities
Am I not understanding this correctly? Could someone explain it to me like you would to a five year old?
CodePudding user response：
This problem can be modeled by generating functions, where each bin yields a polynomial (1 z z2 … zc) where c is the capacity of the bin, and we take the product of the bin polynomials and extract the coefficient of zn.
The straightforward non-recursive dynamic programming algorithm is to evaluate the product from left to right. If needed, you can get fancy and mix and match your multiplication algorithms, especially given that c ≤ 15.