0

Suppose we have N balls and M bins to put them into. The number of outcomes for this can be found using 'stars and bars' method Integer Equations - Stars and Bars. We can also compute all the actual outcomes using the itertools package and get unique outcomes by using sympy.utilities.iterables.multiset_permutations.

If we restrict bin size however to some arbitrary number on [0, N], how could you efficiently compute all the possible outcomes? Is there a better way than computing all outcomes without bin size and then eliminating invalid outcomes afterwards?

For N = 2 and M = 3, the outcomes are {200, 110, 020, 011, 101, 002}.

For example, with N = 3 and M = 3, the outcomes are {300, 210, 120, 021, 012, 030, 201, 102, 003, 111}. But what if we wanted some array b=[3,3,0] specifying max bin size so that the only valid outcomes were {300, 210, 120, 030}?

martineau
  • 119,623
  • 25
  • 170
  • 301
Stevie
  • 326
  • 3
  • 16

1 Answers1

0

You could use a recursive approach placing 0 to maximum balls on the first bin and recursing with the remaining balls on the rest of the bins:

def ballPlacing(N,B):
    if N <= 0: return int(N==0)
    if len(B) == 1:
        return int(N<=B[0])
    total = 0
    for c in range(min(N,B[0])+1):
        total += ballPlacing(N-c,B[1:])
    return total

print(ballPlacing(3,[3,3,3])) # 10
print(ballPlacing(3,[3,3,0])) # 4
Alain T.
  • 40,517
  • 4
  • 31
  • 51