如何生成分配球到箱子的所有组合，包括空分配和满分配？
How to generate all combinations of assigning balls into bins including empty and full assignments?
这似乎是一个已知问题，但我找不到它。我有 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
然后我想把这些组合分配给垃圾箱，但我无法完成。
好的，这是两个箱子的有限解决方案，但是任意数量的（可区分的）球。
首先要找到可以放入 bin 1 (combsBin1) 的球的可能组合。从那里开始，迭代所有这些组合，并通过排除那些已经放入 bin 1 的球来生成球子集。然后对于 combsBin1 中的每个组合，找到填充 bin 2 的所有组合。最后，这些组合的组合（哇，我很抱歉措辞不佳）被存储。
这是一些 Octave（MATLAB 兼容）代码。这绝对不漂亮，可能有助于删除一些分号以检查中间结果。
balls = [NaN 1 2];
bins = [1 2];
finalCombs = {};
% Fill bin 1
combsBin1 = {};
for iBall = 1:numel(balls)-1
if (iBall == 1)
temp = nchoosek(balls, iBall);
else
temp = nchoosek(balls(2:end), iBall);
end
combsBin1 = [combsBin1; mat2cell(temp, ones(size(temp, 1), 1))];
end
% Output
printf('Possible combinations for bin 1 only:\n\n');
printf('Bin 1\n');
printf('-----\n');
for iC = 1:size(combsBin1, 1)
printf('%s\n', num2str(combsBin1{iC, 1}));
end
% Fill bin 2 by iterating all combinations found for bin 1
% and excluding all balls which are already in bin 1.
for iComb = 1:numel(combsBin1)
b = [NaN setdiff(balls(2:end), combsBin1{iComb})];
if (isnan(b))
finalCombs = [finalCombs; [combsBin1{iComb}, {NaN}]];
end
for iBall = 1:numel(b)-1
if (iBall == 1)
temp = nchoosek(b, iBall);
else
temp = nchoosek(b(2:end), iBall);
end
c = mat2cell(temp, ones(size(temp, 1), 1));
for iC = 1:numel(c)
finalCombs = [finalCombs; [combsBin1{iComb}, c(iC)]];
end
end
end
% Output
printf('\n\nPossible combinations for bin 1 and bin 2:\n\n');
printf('Bin 1 Bin 2\n');
printf('----- -----\n');
for iC = 1:size(finalCombs, 1)
str = num2str(finalCombs{iC, 1});
printf('%s', str);
printf('%s', char(32 * ones(1, 15 - length(str))));
printf('%s\n', num2str(finalCombs{iC, 2}));
end
我合并了一个“NaN 球”，因为没有球被放入特定的容器中。通过使用 nchoosek 来增加球的数量，找到一组球的所有可能组合。为了每个组合存储不同数量的球，我需要使用元胞数组，这使得处理更加复杂，代码可能更难理解。
对于两个箱子和两个球，我们得到以下输出：
Possible combinations for bin 1 only:
Bin 1
-----
NaN
1
2
1 2
Possible combinations for bin 1 and bin 2:
Bin 1 Bin 2
----- -----
NaN NaN
NaN 1
NaN 2
NaN 1 2
1 NaN
1 2
2 NaN
2 1
1 2 NaN
如果我们使用三个球，我们得到：
Possible combinations for bin 1 only:
Bin 1
-----
NaN
1
2
3
1 2
1 3
2 3
1 2 3
Possible combinations for bin 1 and bin 2:
Bin 1 Bin 2
----- -----
NaN NaN
NaN 1
NaN 2
NaN 3
NaN 1 2
NaN 1 3
NaN 2 3
NaN 1 2 3
1 NaN
1 2
1 3
1 2 3
2 NaN
2 1
2 3
2 1 3
3 NaN
3 1
3 2
3 1 2
1 2 NaN
1 2 3
1 3 NaN
1 3 2
2 3 NaN
2 3 1
1 2 3 NaN
所以，现在，要将此代码概括为也支持任意数量的箱子，您必须将第二部分（不包括之前已经选择的球等）放入某个迭代过程，也许是递归过程。这可能需要大量工作，但所提出的方法应该是合适的。
希望对您有所帮助！
这是 Matlab 中的一个解决方案，完全 矢量化 。它应该很快。做法是：
- 创建一个矩阵，指示每个球进入哪个 bin（包括没有 bin 的可能性）；
- 收集每个垃圾箱中的球。
第一部分只是 n+1 元素向量与自身 m 次的笛卡尔积。可以使用 dec2base, provided that n is less than 36. If not, it this approach 作为数字基础转换来完成。
第二部分使用 accumarray 高效完成。
m = 2; % data: number of balls
n = 3; % data: number of bins
t = (n+1)^m; % compute number of cases
[~, pos] = ismember(dec2base(0:t-1, n+1), ['1':'9' 'A':'Z']); % each column in this
% matrix refers to a ball, and tells which bin the ball goes to, or zero if no bin
[ii, jj, vv] = find(pos); % ii: combination; jj: ball: vv: bin
result = accumarray([ii vv], jj, [t n], @(x){sort(x).'}); % collect balls of each bin
例子
对于m=2, n=3：
（抱歉使用图片）。
将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]
这似乎是一个已知问题，但我找不到它。我有 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
然后我想把这些组合分配给垃圾箱，但我无法完成。
好的，这是两个箱子的有限解决方案，但是任意数量的（可区分的）球。
首先要找到可以放入 bin 1 (combsBin1) 的球的可能组合。从那里开始，迭代所有这些组合，并通过排除那些已经放入 bin 1 的球来生成球子集。然后对于 combsBin1 中的每个组合，找到填充 bin 2 的所有组合。最后，这些组合的组合（哇，我很抱歉措辞不佳）被存储。
这是一些 Octave（MATLAB 兼容）代码。这绝对不漂亮，可能有助于删除一些分号以检查中间结果。
balls = [NaN 1 2];
bins = [1 2];
finalCombs = {};
% Fill bin 1
combsBin1 = {};
for iBall = 1:numel(balls)-1
if (iBall == 1)
temp = nchoosek(balls, iBall);
else
temp = nchoosek(balls(2:end), iBall);
end
combsBin1 = [combsBin1; mat2cell(temp, ones(size(temp, 1), 1))];
end
% Output
printf('Possible combinations for bin 1 only:\n\n');
printf('Bin 1\n');
printf('-----\n');
for iC = 1:size(combsBin1, 1)
printf('%s\n', num2str(combsBin1{iC, 1}));
end
% Fill bin 2 by iterating all combinations found for bin 1
% and excluding all balls which are already in bin 1.
for iComb = 1:numel(combsBin1)
b = [NaN setdiff(balls(2:end), combsBin1{iComb})];
if (isnan(b))
finalCombs = [finalCombs; [combsBin1{iComb}, {NaN}]];
end
for iBall = 1:numel(b)-1
if (iBall == 1)
temp = nchoosek(b, iBall);
else
temp = nchoosek(b(2:end), iBall);
end
c = mat2cell(temp, ones(size(temp, 1), 1));
for iC = 1:numel(c)
finalCombs = [finalCombs; [combsBin1{iComb}, c(iC)]];
end
end
end
% Output
printf('\n\nPossible combinations for bin 1 and bin 2:\n\n');
printf('Bin 1 Bin 2\n');
printf('----- -----\n');
for iC = 1:size(finalCombs, 1)
str = num2str(finalCombs{iC, 1});
printf('%s', str);
printf('%s', char(32 * ones(1, 15 - length(str))));
printf('%s\n', num2str(finalCombs{iC, 2}));
end
我合并了一个“NaN 球”，因为没有球被放入特定的容器中。通过使用 nchoosek 来增加球的数量，找到一组球的所有可能组合。为了每个组合存储不同数量的球，我需要使用元胞数组，这使得处理更加复杂，代码可能更难理解。
对于两个箱子和两个球，我们得到以下输出：
Possible combinations for bin 1 only:
Bin 1
-----
NaN
1
2
1 2
Possible combinations for bin 1 and bin 2:
Bin 1 Bin 2
----- -----
NaN NaN
NaN 1
NaN 2
NaN 1 2
1 NaN
1 2
2 NaN
2 1
1 2 NaN
如果我们使用三个球，我们得到：
Possible combinations for bin 1 only:
Bin 1
-----
NaN
1
2
3
1 2
1 3
2 3
1 2 3
Possible combinations for bin 1 and bin 2:
Bin 1 Bin 2
----- -----
NaN NaN
NaN 1
NaN 2
NaN 3
NaN 1 2
NaN 1 3
NaN 2 3
NaN 1 2 3
1 NaN
1 2
1 3
1 2 3
2 NaN
2 1
2 3
2 1 3
3 NaN
3 1
3 2
3 1 2
1 2 NaN
1 2 3
1 3 NaN
1 3 2
2 3 NaN
2 3 1
1 2 3 NaN
所以，现在，要将此代码概括为也支持任意数量的箱子，您必须将第二部分（不包括之前已经选择的球等）放入某个迭代过程，也许是递归过程。这可能需要大量工作，但所提出的方法应该是合适的。
希望对您有所帮助！
这是 Matlab 中的一个解决方案，完全 矢量化 。它应该很快。做法是：
- 创建一个矩阵，指示每个球进入哪个 bin（包括没有 bin 的可能性）；
- 收集每个垃圾箱中的球。
第一部分只是 n+1 元素向量与自身 m 次的笛卡尔积。可以使用 dec2base, provided that n is less than 36. If not, it this approach 作为数字基础转换来完成。
第二部分使用 accumarray 高效完成。
m = 2; % data: number of balls
n = 3; % data: number of bins
t = (n+1)^m; % compute number of cases
[~, pos] = ismember(dec2base(0:t-1, n+1), ['1':'9' 'A':'Z']); % each column in this
% matrix refers to a ball, and tells which bin the ball goes to, or zero if no bin
[ii, jj, vv] = find(pos); % ii: combination; jj: ball: vv: bin
result = accumarray([ii vv], jj, [t n], @(x){sort(x).'}); % collect balls of each bin
例子
对于m=2, n=3：
（抱歉使用图片）。
将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]