algorithm - 查找3x3打洞器的所有组合

我当时在狂欢节上，他们在每个地方都用特殊的打孔器标记您的程序。打孔器是3x3空间的网格。在每个空间中，都有一个可以刺破您的纸张的别针，或者没有。这让我想知道您可以使用此工具制作多少种不同的图案。我的第一个念头是:2 ^ 9 = 512，但所有9个无针位都不是一拳，所以真的:511。

然后复杂性打击了我。尤其是由于 worker 们在打孔纸张时并不十分小心，因此看起来都是虚假的:

x..  .x.  ...  etc.
.x.  x..  .x.
...  ...  ..x

问题:如何编写测试以说明旋转和移位？

到目前为止的勤奋和想法:

Binary看起来像是此等式的明显部分

找到唯一模式后，将其存储在内存中，以便将来可以针对它测试模式

有4种旋转可能性。 编辑:我所说的“旋转”是指可以采用任何形状并将其旋转90度。考虑左上角为点的图案。您可以将其旋转90度，并在右上角获得点。再次执行此操作，它位于右下角。同样，它在左下角。使用纯2 ^ 9计算，它们是4个不同的组合。对于这个问题，这些正是我要清除的重复项。

对于每次旋转，有25种方法可使3x3网格重叠:

重叠部分:

/ = the spaces in the new one to test
\ = the spaces in a verified unique one

1               2               25
/ / / . . . .   . / / / . . .   . . . . . . .
/ / / . . . .   . / / / . . .   . . . . . . .
/ / X \ \ . .   . / X X \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ X / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

如果任一模式包含不在重叠区域中的图钉，则不需要测试重叠。按位与可以在这里提供帮助。

如果将两个模式中的每个模式的每个位置都转换为字符串，则只需检查

是否相等

可以将前两个想法结合起来以提高效率吗？

最佳答案

我们只需要考虑在第一行和第一栏中打孔的模式。如果第一行为空，则可以向上移动图案。如果第一列为空，则可以向左移动图案。无论哪种情况，我们都可以得出我们考虑过的相似模式。

对于这些模式，我们需要检查旋转的版本是否相同。为此，我们最多进行三个90度旋转，可能会向左移动以删除前导的空列(第一行永远不会为空)，并找到具有最低数值的模式。

然后，我们可以将此值添加到仅保留唯一值的哈希集。

不包括空模式，因为其所有行均为空。

为了实现这一点，我们将模式编码为连续的位:

012
345
678

我们将需要的操作非常简单:

Test for an empty row:    (n & 7) == 0     // bits 0,1,2 not set
Test for an empty column: (n & 73) == 0    // bits 0,3,6 not set
Shift pattern up:         n -> (n >> 3)
Shift pattern left:       n -> (n >> 1)

最棘手的部分是轮换，它实际上只是在重新排列所有位:

n -> ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
   + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
   + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);

在C#中:

public static int Count3x3() {
    HashSet<int> patterns = new HashSet<int>();
    for (int i = 0; i < 512; i++) {
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        int nLowest = i;
        int n = i;
        do {
            nLowest = Math.Min(nLowest, n);
            n = ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
                + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
                + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);
            while ((n & 73) == 0)
                n >>= 1;
        } while (n != i);
        patterns.Add(nLowest);
    }
    return patterns.Count;
}

该函数返回116。在我的机器上花费的时间为0.023ms。

编辑:使用4个观察值，您可以得到额外的7倍改进:

我们可以使用简单的访问数组而不是哈希集。如果以前看过某个模式，我们就不算。这也消除了跟踪内循环中“最低”模式的需要。如果访问了某个模式，那么其最低旋转的模式也将被访问。

如果我们没有180度旋转对称性，那么第3次旋转将不会产生原始图案。始终会进行第4轮旋转，因此没有必要。

旋转表达式可以稍微简化。

因此，如果应用这些观察结果并展开内部do循环，则会得到以下结果:

static int Rotate(int n) {
    n = ((n & (1+32)) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
        + ((n & (8+256)) >> 2) + (n & 16)
        + ((n & 64) >> 6) + ((n & 128) >> 4);
    while ((n & 73) == 0)
        n >>= 1;
    return n;
}
public static int Count3x3_3() {
    bool[] visited = new bool[512];
    int count = 0, r;
    for (int i = 0; i < 512; i++) {
        if (visited[i])
            continue;
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        count++;
        if ((r = Rotate(i)) == i) continue;
        visited[r] = true;
        if ((r = Rotate(r)) == i) continue;
        visited[r] = true;
        visited[Rotate(r)] = true;
    }
    return count;
}

这在同一台机器上运行大约3μs。

关于algorithm - 查找3x3打洞器的所有组合，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7653428/