时间戳

首页 > 解决方案 > 5*12 网格中所有唯一组合的算法

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

问题描述

我正在寻找一种算法或我的问题的名称（我认为这是非常古老的并且没有什么新东西）。我想在 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 万个唯一组合。

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

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

标签： arraysalgorithmgriduniquebinomial-coefficients

解决方案

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

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

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

推荐阅读