看来这是一个已知的问题,但我找不到。我有m
球和n
垃圾桶。我想生成将球放入箱中的所有可能组合,包括完整和空的分配,即,一个箱可能是空的或可能包含所有球(请参见下面的示例)。
例如,对于m=n=2
,我发现:
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.
如何在Python中生成这些组合(例如)?您可以提供伪代码或所需的任何编程语言。
我首先生成所有组合,例如
x
1
2
1,2
然后我想将这些组合分配到垃圾箱,但我无法完成。
对于将m个球放入n个仓中,有n ^ m个组合。但是当您接受不向m-1个球放球时,您的问题的答案是m ^ 0 + mC1 * n ^ 1 + mC2 * n ^ 2 + ...的总和。mCm * n ^ m
例如。将3个球放入3个箱中,总数为1 + 3 * 3 + 3 * 9 + 1 * 27 = 64
Python解决方案。
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是完整列表,其中第一部分是使用球,第二部分是使用箱。
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] = 0个球的组合
tmp [1] = 1个球的组合
tmp [2] = 2个球的组合
tmp [3] = 3个球的组合
您可以使用以下命令解压缩tmp
[item for sublist in tmp for item in sublist]
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句