5*12 网格中所有唯一组合的算法

Question

我正在寻找我的问题的算法或名称（我认为这是非常古老的，没有什么新的）。我想在 5x12 网格中找到 5 个填充单元格的所有唯一组合。

示例：

1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0


1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|1|0|0|0|0|0|0|0|0|0


1|1|1|1|1|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0

this is also valid

等等。每个占用的单元格将表示为 (X,Y)-Tuple

独特组合数量的相应公式是 n over k - 二项式系数（或类似的东西），如果我没记错的话，大约是 510 万个独特组合。

此处或其他平台上的大多数其他类似问题都以某种方式限制了每一行必须恰好占用一个单元格。对于我的特殊情况，这是不正确的以及我的问题的原因。

这是我的第一个问题，我希望有人能帮助我解决这个问题，因为我找不到系统方法的想法

Answer 1

我建议您使用这个简单易懂的解决方案：首先，给每个单元格一个索引，这样我们就可以讨论 60 个单元格长度列表而不是二维板。我希望你初始化这样一个索引列表：[1, 2, 3... 59, 60] 现在，您基本上需要这些索引的每个 k 大小（在您的例子中是五个）组合。剩下的就很简单了。使用此代码：

def findsubsets(s, n): 
    return list(itertools.combinations(s, n))

虽然 s 是您的列表，n 是 k（5 为您）。此函数 returns 列表中 5 个数字的所有可能组合。使用每个组合，用 1 填充正确的单元格，用 0 填充其余单元格。希望对您有所帮助。祝你好运！

5*12 网格中所有唯一组合的算法

Algorithm for all unique combinations in a 5*12 grid

arrays

algorithm

grid

unique

binomial-coefficients