找到 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 / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

• 如果任一图案包含不在重叠区域中的引脚，则无需测试重叠。按位与可以在这里提供帮助。
• 如果将 2 个模式中的每一个的每个位置都放入字符串中，则只需检查相等性
• 即可 将前面的两个想法结合起来以提高效率吗？

Answer 1

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

对于这些模式，我们需要检查旋转后的版本是否相同。为此，我们应用最多 3 个 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. 旋转表达式可以稍微简化。

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

Answer 2

我的解决方案：116 个独特的形状

当测试 2 个形状是否相等时，比较引脚数量可以节省大量时间。但我最大的突破是意识到所有这 25 个位置都可以用以下方式替换：对于要检查相等性的两个 3x3 形状中的每一个，将行与两个零连接起来，然后修剪前导零和尾随零。连接零是为了防止环绕。示例：

010 => 01000 => 0100010100000 => 1000101
101    10100
000    000

000 => 00000 => 0000001000101 => 1000101
010    01000
101    101

然后只需测试结果是否相等。这是 4 次简单迭代（每次旋转 1 次），而不是 100 次（25 个位置 * 4 次旋转）更复杂的迭代。

---

时间：
仅字符串：

• 强力，每次旋转的所有 25 个位置：2018ms
• ...00...00... 修剪：75ms
• 更多优化：59ms

OOP 和更好的缓存：17ms

Answer 3

您并不是要求计算平移和旋转之前的独特模式的数量，而是要求进行一致性测试。

选择 3x3 网格的位串表示形式。我会从上到下逐行选择。通过在相应的打孔位置设置一个位，我们现在可以将 9 位整数映射到打孔模式（反之亦然）。

对于任何特定的表示，我们可以设计表示旋转和平移的位调整操作。在某些模式上执行某些翻译是非法的，因为我们希望避免“环绕”。

正如旋转和平移是可逆的一样，我们的操作也是可逆的。如果两个动作将模式 A 映射到 B，然后将 B 映射到 C，我们当然可以组合动作来进行从 A 到 C 的变换。什么都不做（恒等变换）也是合法的，因此我们可以从 A 到达 A。因此，通过变换是打孔图案上的等价关系，因此等价图案划分了空间。

通过为每个打孔模式分配正整数分数的方法，我们可以调用良序原则：包含该模式的等价类将包含最低分数的唯一模式（包括平移和旋转）。我们将选择这个最少的模式作为等价类的代表。如果两个模式具有相同的等价类代表，则它们必然是全等的。如果不一致，则它们必然不一致。

给定一个模式，我们如何找到其最小权重代表？通过检查，贪婪算法并不能保证有效。我们可以使用无数启发式优化算法中的一种，或者我们可以注意到我们只推动 9 位并彻底搜索空间。应该注意的是，出于同样的原因，这很适合计算一次，然后永远推入查找表中。

这是详尽的搜索。请注意，通过适当的缓存，它仍然相当快（不到一秒）。

#!/usr/bin/env ruby

require 'set'

class PunchPattern < String
  @@representatives = Hash.new do |h, k|
    equivalence_class = k.closure
    representative = equivalence_class.min

    k.closure.each do |node|
      h[node] = representative
    end

    representative
  end

  def initialize(s)
    raise "9 digits of 0 and 1, pls" unless s =~ /[01]{9}/
    super
  end

  def left
    return nil unless self =~ /0..0..0../
    PunchPattern.new([self[1...3], 0, self[4...6], 0, self[7...9], 0].join)
  end

  def right
    return nil unless self =~ /..0..0..0/
    PunchPattern.new([0, self[0...2], 0, self[3...5], 0, self[6...8]].join)
  end

  def up
    return nil unless self =~ /000....../
    PunchPattern.new([self[3...9], 0, 0, 0].join)
  end

  def down
    return nil unless self =~ /......000/
    PunchPattern.new([0, 0, 0, self[0...6]].join)
  end

  def turn
    PunchPattern.new([2, 5, 8, 1, 4, 7, 0, 3, 6].collect { |i| self[i].chr }.join)
  end

  def closure
    seen = Set.new([])
    frontier = Set.new([self])

    until frontier.empty?
      node = frontier.first
      frontier.delete(node)
      seen.add(node)

      %w{left right up down turn}.collect do |motion|
        node.send motion
      end.compact.each do |neighbor|
        frontier.add(neighbor) unless seen.include? neighbor
      end
    end

    seen
  end

  def representative
    self.class.representatives[self]
  end

  def self.representatives
    @@representatives
  end

end

(0...512).collect do |p|
  p = PunchPattern.new(p.to_s(2).rjust(9, '0'))
  [p.representative, p]
end.inject(Hash.new { |h, k| h[k] = [] }) do |h, pair|
  h[pair.first] << pair.last
  h
end.sort_by { |pair| pair.first }.each do |representative, patterns|
  puts patterns.collect { |p| p[0...3] + " " }.join
  puts patterns.collect { |p| p[3...6] + " " }.join
  puts patterns.collect { |p| p[6...9] + " " }.join
  puts
end

puts "#{PunchPattern.representatives.values.uniq.size} total congruence classes"

生成

$ ./congruence.rb 
000 
000 
000 

000 000 000 000 000 000 001 010 100 
000 000 000 001 010 100 000 000 000 
001 010 100 000 000 000 000 000 000 

000 000 000 000 000 000 000 001 010 011 100 110 
000 000 001 010 011 100 110 001 010 000 100 000 
011 110 001 010 000 100 000 000 000 000 000 000 

000 000 001 010 100 101 
000 101 000 000 000 000 
101 000 001 010 100 000 

000 000 001 010 100 111 
000 111 001 010 100 000 
111 000 001 010 100 000 

000 000 000 000 001 010 010 100 
001 010 010 100 010 001 100 010 
010 001 100 010 000 000 000 000 

000 000 000 000 000 000 000 000 001 010 010 011 011 100 110 110 
001 010 010 011 011 100 110 110 011 011 110 001 010 110 010 100 
011 011 110 001 010 110 010 100 000 000 000 000 000 000 000 000 

000 001 010 100 
001 100 000 000 
100 000 001 010 

000 000 001 010 011 100 101 110 
001 101 101 000 000 000 100 000 
101 100 000 011 001 110 000 010 

000 000 001 010 010 011 100 100 
001 011 110 001 010 100 010 100 
110 100 000 001 001 000 010 010 

000 000 001 010 011 100 110 111 
001 111 111 010 001 100 010 100 
111 100 000 011 001 110 010 000 

000 000 001 010 010 010 100 101 
010 101 010 001 100 101 010 010 
101 010 001 010 010 000 100 000 

000 000 001 010 010 010 100 111 
010 111 011 011 110 111 110 010 
111 010 001 010 010 000 100 000 

000 000 011 110 
011 110 011 110 
011 110 000 000 

000 000 010 011 011 100 101 110 
011 101 001 010 101 010 110 100 
101 110 011 001 000 110 000 010 

000 010 011 100 
011 011 110 110 
110 001 000 010 

000 000 010 011 011 100 110 111 
011 111 011 011 111 110 110 110 
111 110 011 001 000 110 010 000 

000 001 010 100 
100 000 000 001 
001 010 100 000 

000 000 001 001 010 010 100 110 
100 110 001 010 010 100 011 001 
011 001 010 010 100 100 000 000 

000 000 001 010 011 100 101 110 
100 101 000 000 000 101 001 000 
101 001 011 110 010 000 000 100 

000 000 001 010 011 100 110 111 
100 111 001 010 010 111 100 001 
111 001 011 110 010 000 100 000 

000 000 001 010 011 101 110 110 
101 110 010 100 001 011 010 101 
011 101 011 110 010 000 100 000 

000 011 101 110 
101 000 101 000 
101 011 000 110 

000 000 011 011 101 110 110 111 
101 111 001 010 111 010 100 101 
111 101 011 011 000 110 110 000 

000 001 010 110 
110 011 110 011 
011 010 100 000 

000 000 001 010 011 110 110 111 
110 111 011 110 011 110 111 011 
111 011 011 110 010 100 000 000 

000 011 110 111 
111 011 110 111 
111 011 110 000 

001 100 
000 000 
100 001 

001 100 101 101 
000 000 000 000 
101 101 001 100 

001 011 100 100 
000 000 001 100 
110 100 001 001 

001 100 101 111 
000 100 001 000 
111 101 001 100 

001 001 100 110 
001 100 000 000 
100 100 011 001 

001 100 101 111 
001 000 100 000 
101 111 100 001 

001 011 100 110 
001 100 100 001 
110 100 011 001 

001 100 111 111 
001 100 001 100 
111 111 001 100 

001 100 
010 010 
100 001 

001 100 101 101 
010 010 010 010 
101 101 001 100 

001 011 100 100 
010 010 011 110 
110 100 001 001 

001 100 101 111 
010 110 011 010 
111 101 001 100 

001 001 100 110 
011 110 010 010 
100 100 011 001 

001 100 101 111 
011 010 110 010 
101 111 100 001 

001 011 100 110 
011 110 110 011 
110 100 011 001 

001 100 111 111 
011 110 011 110 
111 111 001 100 

001 010 100 101 
100 000 001 000 
001 101 100 010 

001 010 010 100 
100 001 100 001 
010 100 001 010 

001 010 101 110 
100 100 001 001 
011 101 010 100 

001 101 101 110 
100 000 001 000 
101 011 100 101 

001 011 100 110 
100 001 001 100 
110 100 011 001 

001 101 110 111 
100 001 100 001 
111 011 101 100 

001 010 100 111 
101 000 101 000 
001 111 100 010 

001 010 010 110 
101 100 101 001 
010 011 100 010 

001 010 110 111 
101 100 101 001 
011 111 100 010 

001 110 
101 000 
100 011 

001 101 110 111 
101 101 000 000 
101 100 111 011 

001 011 110 110 
101 101 001 100 
110 100 011 011 

001 110 111 111 
101 100 001 101 
111 111 011 100 

001 010 100 101 
110 010 011 010 
001 101 100 010 

001 010 010 100 
110 011 110 011 
010 100 001 010 

001 010 101 110 
110 110 011 011 
011 101 010 100 

001 101 101 110 
110 010 011 010 
101 011 100 101 

001 011 100 110 
110 011 011 110 
110 100 011 001 

001 101 110 111 
110 011 110 011 
111 011 101 100 

001 010 100 111 
111 010 111 010 
001 111 100 010 

001 010 010 110 
111 110 111 011 
010 011 100 010 

001 010 110 111 
111 110 111 011 
011 111 100 010 

001 110 
111 010 
100 011 

001 101 110 111 
111 111 010 010 
101 100 111 011 

001 011 110 110 
111 111 011 110 
110 100 011 011 

001 110 111 111 
111 110 011 111 
111 111 011 100 

010 011 100 101 
001 100 001 100 
101 001 110 010 

010 010 011 100 
001 101 100 101 
110 001 010 010 

010 011 100 111 
001 101 101 100 
111 001 110 010 

010 011 100 101 
011 110 011 110 
101 001 110 010 

010 010 011 100 
011 111 110 111 
110 001 010 010 

010 011 100 111 
011 111 111 110 
111 001 110 010 

010 
101 
010 

010 010 011 110 
101 101 101 101 
011 110 010 010 

010 011 101 110 
101 100 101 001 
101 011 010 110 

010 011 110 111 
101 101 101 101 
111 011 110 010 

010 
111 
010 

010 010 011 110 
111 111 111 111 
011 110 010 010 

010 011 101 110 
111 110 111 011 
101 011 010 110 

010 011 110 111 
111 111 111 111 
111 011 110 010 

011 100 101 101 
000 001 000 100 
101 101 110 001 

011 100 
000 101 
110 001 

011 100 101 111 
000 101 101 000 
111 101 001 110 

011 100 101 111 
001 001 100 100 
101 111 110 001 

011 011 100 110 
001 100 101 101 
110 110 011 001 

011 100 111 111 
001 101 100 101 
111 111 110 001 

011 100 101 101 
010 011 010 110 
101 101 110 001 

011 100 
010 111 
110 001 

011 100 101 111 
010 111 111 010 
111 101 001 110 

011 100 101 111 
011 011 110 110 
101 111 110 001 

011 011 100 110 
011 110 111 111 
110 110 011 001 

011 100 111 111 
011 111 110 111 
111 111 110 001 

011 101 101 110 
100 001 100 001 
101 110 011 101 

011 101 110 111 
100 101 101 001 
111 011 101 110 

011 101 110 111 
101 101 001 100 
101 110 111 011 

011 110 
101 101 
110 011 

011 110 111 111 
101 101 101 101 
111 111 011 110 

011 101 101 110 
110 011 110 011 
101 110 011 101 

011 101 110 111 
110 111 111 011 
111 011 101 110 

011 101 110 111 
111 111 011 110 
101 110 111 011 

011 110 
111 111 
110 011 

011 110 111 111 
111 111 111 111 
111 111 011 110 

101 
000 
101 

101 101 101 111 
000 001 100 000 
111 101 101 101 

101 101 111 111 
001 100 001 100 
111 111 101 101 

101 
010 
101 

101 101 101 111 
010 011 110 010 
111 101 101 101 

101 101 111 111 
011 110 011 110 
111 111 101 101 

101 111 
101 000 
101 111 

101 111 111 111 
101 001 100 101 
111 111 111 101 

101 111 
111 010 
101 111 

101 111 111 111 
111 011 110 111 
111 111 111 101 

111 
101 
111 

111 
111 
111 

117 total congruence classes

..117 个类。

Answer 4

首先，我们可以将除了平移之外的等效的两个拳击视为彼此的旋转。想象一下冲孔图案位于球体的表面上：我们可以通过沿水平轴和垂直轴旋转球体（因为它握在我们手中）来“平移”它。

两个冲孔相当于旋转（例如 90 度旋转 ） -度转动）也可以通过我们沿第三个剩余轴旋转球体来捕获。

现在我们将问题简化为“球体表面有多少种独特的打孔图案，直至旋转？”为了像这样计算对称性的唯一对象，您需要 非 Burnside 引理。 这本书是一本很好的入门书。

Answer 5

我不认为这就像球体情况，因为你不能绕边缘旋转？ IE：

XOO
XXO
XOO

不同

OOX
XOX
OOX

与我尝试在纸上手工计数以查看得到的结果 。考虑 2x2 的情况 - 您有 1 个 0 个点、1 个 1 个点、2 个 2 个点（相邻或对角线）、1 个 3 个点和 1 个 4 个点；总共 5 个（如果您忽略空箱，则为 4 个）。请注意，枚举是对称的，因为将空空格算作满空格是相同的。对于 3x3 的情况，我得到了这个：

C(0) = 1
C(1) = 1
C(2) = 5
C(3) = 10
C(4) = 21

然后通过对称性，21,10,5,1,1，

我得到 76。我很容易算错，特别是在 4/5 的情况下。

我能想到的自动枚举这些的唯一方法是移动和旋转模式，看看它们是否与之前枚举的模式匹配。移动是很棘手的，因为你只能移动直到“碰撞”到边缘。

Answer 6

值得指出的是，如果您确实需要每个形状“看起来”独特，那么无论它如何旋转或移动，您都没有什么可供选择的。例如，一拳，无论它在网格中的哪个位置，看起来总是一样的。此外，假设正方形网格和圆形引脚，并假设微小的间距差异 (√2) 不显着，那么对角线上的 2 个孔将看起来与两个相邻的引脚相同，因为观察者看到的只是靠近在一起的 2 个孔。同样，对角线中的 3 个看起来就像直线中的 3 个，这极大地限制了您的选择。

请注意，对于我们所追求的内容，形状可能比组合更好，因为我们不关心实际的组合是什么，只关心最终的形状是什么纸。

我认为我们可以假设，无论形状如何，它都可以旋转和移动，从而使左上角的销钉被冲孔（特别是如果您允许 45 度旋转），这使我们能够进一步缩小搜索范围。我们使用以下规则来完成此操作：

1. 如果任何角被打孔，则旋转网格直到打孔的角位于左上角，
2. 否则将图案尽可能向上和向左移动。
3. 重复步骤 1
4. 如果我们走到这一步，那么我们知道只有顶部中间位置被打孔（因为我们知道两个角都没有），在这种情况下，我们将图案旋转 45 度，使顶部中间位置现在成为左上角。量子ED。

我用笔和纸快速地强力搜索了可能的形状，看起来可行的选项列表非常小，您可以在几分钟内将它们全部列出。

Answer 7

我不太清楚关于旋转的这一部分，但对于这种情况：

有 3x3=9 个孔和 10 个情况，每次只能发生一种情况：

Case 1 = no holes
Case 2 = one hole
...
Case 10 = 9 holes

那么它会像这样使用组合公式 C(n,k) :

总计 = C(9,0)+C(9,1)+....+C(9,9)

这是对 n 个元素的 k 个不同组合求和。

总计 = 1+9+36+84+126+126+84+36+9+1 = 512

我认为你是对的，512似乎是正确的，理论上无针也被定义为一个组合，如果你不想的话它只是将其删除以获得 511。

所有这些情况都是单独发生的，因此我们添加不同的情况。

如果它们同时发生，例如计算 3 名员工在纸上打孔一次的组合或计算一名员工在纸上标记 3 次的组合，那么它会变得更复杂，根据 nxm 规则应该是 512 * 512 * 512。

简单显示中的 m*n 规则是：

我有 4=m 个口袋和 2=n 只手：

my_left * 4（口袋）=4 my_right * 4（口袋）=4

总计= 4+4=4*2=m*n

一次只能一只手进入口袋或者一名员工只能与一种组合配对另一个员工的组合，这就是我们采用 m*n 规则的确切原因。

这是我的想法，我不是数学家，也不声称100%正确，这只是我在概率课程中记得的。

我并不声称100%正确，这只是我记得的概率课程。

---

至于模式重叠、检查是否已经找到模式等，我根本不会打扰，因为伪代码中有很多算法可以生成组合。由于它们生成，因此无需检查重叠或任何内容。

毕竟，这就是生成的意思，它被设计为先验地找到所有结果，只需让它运行即可。

我曾经发现过一种比简单组合更罕见的算法，当我将其转换为 php 时，它完美地完成了工作，无需担心重叠或其他任何问题。