It seems that this is some known problem but I cannot find it. I have m balls and n bins. I would like to generate all possible combinations of putting the balls into the bins including full and empty assignments, i.e., a bin maybe empty or may contain all balls (see the example below).
For example, for m=n=2, I found:
1 x bin 1 contains ball 1, bin 2 contains nothing.
x 1 bin 1 contains nothing, bin 2 contains ball 1.
2 x bin 1 contains ball 2, bin 2 contains nothing.
x 2 bin 1 contains nothing, bin 2 contains ball 2.
1,2 x bin 1 contains balls 1 and 2, bin 2 contains nothing.
x 1,2 bin 1 contains nothing, bin 2 contains balls 1 and 2.
1 2 bin 1 contains ball 1, bin 2 contains ball 2.
2 1 bin 1 contains ball 2, bin 2 contains ball 1.
x x bin 1 contains nothing, bin 2 contains nothing.
How can I generate these combinations in Python (for example)? You can provide a pseudo-code or any programming language you wish.
I start by generating all combinations like
x
1
2
1,2
then I was thinking to assign these combinations to the bins but I could not finish it.
for m balls to be put into n bins, there are n^m combinations. But as you accept putting no balls to m-1 balls, the answer to your question is summation of m^0 + mC1 * n^1 + mC2 * n^2 + .... mCm * n^m
eg. for 3 balls into 3 bins, the total number is 1 + 3*3 + 3*9 + 1*27 = 64
Python Solution.
import itertools
#let bins be 'ABC', but u can have your own assignment
bins = 'ABC'
balls = '123'
tmp = []
for no_ball_used in range(len(balls)+1):
bin_occupied = [''.join(list(i)) for i in itertools.product(bins,repeat=no_ball_used)]
ball_used = [''.join(list(i)) for i in itertools.combinations(balls,no_ball_used)]
solution = [i for i in itertools.product(ball_used,bin_occupied)]
tmp.append(solution)
tmp is the complete list, where first part is ball used, and second part is bin used.
print(tmp)
[[('', '')], [('1', 'A'), ('1', 'B'), ('1', 'C'), ('2', 'A'), ('2', 'B'), ('2', 'C'), ('3', 'A'), ('3', 'B'), ('3', 'C')], [('12', 'AA'), ('12', 'AB'), ('12', 'AC'), ('12', 'BA'), ('12', 'BB'), ('12', 'BC'), ('12', 'CA'), ('12', 'CB'), ('12', 'CC'), ('13', 'AA'), ('13', 'AB'), ('13', 'AC'), ('13', 'BA'), ('13', 'BB'), ('13', 'BC'), ('13', 'CA'), ('13', 'CB'), ('13', 'CC'), ('23', 'AA'), ('23', 'AB'), ('23', 'AC'), ('23', 'BA'), ('23', 'BB'), ('23', 'BC'), ('23', 'CA'), ('23', 'CB'), ('23', 'CC')], [('123', 'AAA'), ('123', 'AAB'), ('123', 'AAC'), ('123', 'ABA'), ('123', 'ABB'), ('123', 'ABC'), ('123', 'ACA'), ('123', 'ACB'), ('123', 'ACC'), ('123', 'BAA'), ('123', 'BAB'), ('123', 'BAC'), ('123', 'BBA'), ('123', 'BBB'), ('123', 'BBC'), ('123', 'BCA'), ('123', 'BCB'), ('123', 'BCC'), ('123', 'CAA'), ('123', 'CAB'), ('123', 'CAC'), ('123', 'CBA'), ('123', 'CBB'), ('123', 'CBC'), ('123', 'CCA'), ('123', 'CCB'), ('123', 'CCC')]]
tmp[0] = combination of 0 balls
tmp[1] = combination of 1 balls
tmp[2] = combination of 2 balls
tmp[3] = combination of 3 balls
You can unpack tmp with
[item for sublist in tmp for item in sublist]