algorithm - 在具有一组连续 1 的二维数组中查找所有可能的位排列

Question

下面我表示了二维位数组中的 2 个位排列(1 为红色)。左边的矩阵有一组连续的 1，但右边的矩阵有 2。

我想遍历这样一个数组中二进制值的所有可能排列，该数组具有一组连续的 1。我知道对于像上面这样的 10×7 网格，当你包含非连续排列时，有 2^{(10 × 7)} 排列，但我希望通过排除非连续排列我会能够在合理的 CPU 时间内全部完成。

说到合理性，我也对确定有多少排列是连续的算法感兴趣。

我的问题与这些相似但又不同:

• 2D Bit matrix with every possible combination
• Finding Contiguous Areas of Bits in 2D Bit Array

感谢任何帮助。我有点卡住了。

Answer 1

所以，我发现 OEIS(整数序列在线百科全书)有一个来自 n = 0..7 的序列，表示“所有 1 连接的非零 n X n 二进制数组的数量” (A059525)。除了固定为 1 个单元格宽度(triangular numbers)或 2 的网格外，它们不提供任何公式。或 3细胞宽。有一个 sequence for 4 x n也是，但没有公式。