找到3x3打孔的所有组合

Question

我参加了一个狂欢节,在每个地方,他们用特殊的打孔标记你的节目.打孔器是3x3空间的网格.在每个空间中,有一个针刺穿你的纸张或没有.这让我想知道你可以使用这个工具制作多少种不同的模式.我的第一个想法是:2 ^ 9 = 512,但是所有9个空间都是无针的并不是真正的一拳,所以真的:511.

然后复杂性打击了我.特别是因为工人们在打纸时并不是那么小心,所以这些看起来都很明显:

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

问题:如何编写测试以考虑轮换和转换？

---

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

• 二元感觉就像这个等式的一个明显的部分
• 找到唯一模式后,将其存储在内存中,以便可以对其进行未来模式测试
• 有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 / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

• 如果任一模式包含不在重叠区域中的引脚,则不需要测试重叠.按位AND可以在这里提供帮助.
• 如果将2个模式中的每个模式的每个位置都放入字符串中,则可以检查是否相等
• 这两个想法可以结合起来提高效率吗？

Answer 1

我们只需要考虑第一行和第一列中有冲压的模式.如果第一行为空,则可以向上移动模式.如果第一列为空,则可以向左移动图案.在任何一种情况下,我们都可以得到一个类似的模式,我们会考虑.

对于这些模式,我们需要检查旋转版本是否相同.我们通过应用最多三次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倍改进:

1. 我们可以使用简单的访问数组而不是哈希集.如果之前看过一个模式,我们就不算数了.这也消除了跟踪内环中"最低"模式的需要.如果访问了模式,那么也会访问其最低旋转模式.
2. 如果我们没有180度旋转对称性,那么第3次旋转将不会产生原始图案.总是第四次旋转所以没必要.
3. 旋转表达式可以略微简化.

因此,如果我们应用这些观察并展开内部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.