找出3x3 holepunch的所有组合

我参加了一个狂欢节，他们在每个地方都用一个特殊的打孔器标记你的节目。打孔机是一个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 / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /

如果任何一个图案包含一个不在重叠区域的引脚，则不需要测试重叠。按位与可以在这里提供帮助。
如果你把两个模式中的每个位置都变成字符串，你可以检查是否相等
前两种思路能否结合起来提高效率?

我们只需要考虑在第一行和第一列中有冲孔的模式。如果第一行为空，则模式可以向上移动。如果第一列为空，则模式可以向左移动。在任何一种情况下，我们都可以推导出我们所考虑的类似模式。

对于这些模式，我们需要检查旋转后的版本是否相同。我们通过应用最多三次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。

EDIT:您可以通过使用4个观察结果获得额外的7倍改进:

我们可以使用一个简单的访问数组来代替哈希集。如果之前发现了某种模式，我们就不计算了。这也消除了在内部循环中跟踪"最低"模式的需要。如果访问了一个模式，那么也会访问它的最低旋转模式。
如果我们没有180度旋转对称，那么第三次旋转不会产生原始图案。第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。

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

当测试两个形状是否相等时，比较引脚的数量可以节省很多时间。但我最大的突破是意识到所有这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……修剪:75 ms
更多优化:59ms

OOP和更好的缓存:17ms

您不是在要求计算到平移和旋转为止的唯一模式的数量，而是要求进行一致性测试。

选择3x3网格的位字符串表示形式。我选择一行一行，从上到下。通过设置一个位，它对应的孔被打孔，我们现在可以将9位整数映射到打孔模式(反之亦然)

对于任何特定的表示，我们都可以实现表示旋转和平移的位篡改操作。有些翻译在某些模式上执行是非法的，因为我们希望避免"绕行"。

正如旋转和平移是可逆的一样，我们的操作也是可逆的。如果两个运动将模式A映射到B，再将B映射到C，我们当然可以将两个运动组合成一个从A到C的变换。不做任何事情(恒等变换)也是合法的，因此我们可以从A得到A。因此变换的可达性是冲孔模式上的等价关系，因此等价模式划分了空间。

有了给每个打孔模式赋正整数分数的方法，我们就可以调用良序原则:包含该模式的等价类将包含一个唯一的最小分数的模式(包括平移和旋转)。我们将选择这个最小的模式作为等价类的代表。如果两个模式具有相同的等价类代表，则它们必然是全等的。如果它们不一致，则它们必然不一致。

给定一个模式，我们如何找到它的最小权值代表?通过检查，贪婪算法不能保证工作。我们可以使用无数种启发式优化算法中的一种，或者我们可以注意到我们只推入9位并彻底搜索空间。值得注意的是，出于同样的原因，它可以很好地计算一次，然后永远塞到查找表中。

这是穷举搜索。注意，如果使用适当的缓存，它仍然非常快(不到1秒)。

#!/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节课。

首先，我们可以将两个除平移外相等的冲头视为彼此的旋转。想象一下，冲孔图案在一个球体的表面上:我们可以通过沿着水平和垂直轴旋转球体来"平移"它(就像它在我们手中一样)。

相当于旋转的两个冲头(如90度转弯)也可以通过我们沿着第三个轴旋转球体来捕获。

现在我们已经将问题简化为"球体表面上有多少种独特的冲孔模式，直到旋转?"为了计算像这样对称的唯一对象，你需要非伯恩赛德引理。这本书是一本很好的入门书。

我不认为这是像球体的情况，因为你不能围绕边缘旋转?即:

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的情况下。

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

值得指出的是，如果你真的需要每个形状"看起来"独特，无论它如何旋转或移动，你有很少的选择。例如，一个单拳，无论它在网格中的位置，看起来总是一样的。此外，假设方形网格和圆形引脚，并且假设较小的间距差异(√2)是微不足道的，那么对角线上的两个孔将看起来与相邻的两个引脚相同，因为所有观看者看到的都是两个紧挨着的孔。同样，对角线上的3看起来就像直线上的3，这极大地限制了你的选择。

请注意，shape可能比combination更适合描述我们所追求的东西，因为我们不关心实际的组合是什么，只关心纸上的结果形状是什么。

我认为我们可以假设，无论什么形状，它都可以旋转和移动，这样左上角的插销就可以打孔了(特别是如果你允许45度旋转的话)，这让我们可以进一步缩小搜索范围。我们使用以下规则完成此操作:

如果任何角被打孔，旋转网格，直到打孔的角位于左上角
否则，将模式尽可能地向上和向左移动。
重复步骤1
如果我们到这里，那么我们知道只有顶部中间的位置被打孔(因为我们知道两个角都没有打孔)，在这种情况下，我们将图案旋转45度，使顶部中间现在是左上角。QED。

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

我不太明白关于旋转的这一部分，但是对于这种情况:

有3x3=9个洞和10个案例，每次只能发生一个案例:

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

然后是这样的组合公式C(n,k):

Total = C(9,0)+C(9,1)+....+C(9,9)

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

Totol = 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(pockets)=4 my_right * 4(pockets)=4
= 4 + 4 = 4 * 2 =总m * n

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

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

我并不是说我100%正确，这只是我记得的概率过程。

至于模式重叠，检查模式是否已经发现等，我根本不会打扰，因为在伪代码中有这么多生成组合的算法。因为它们可以生成，所以不需要检查重叠或其他东西。

毕竟这就是generate的意思，它被设计为先验地查找所有结果，就让它运行吧。

我曾经发现了一个比简单组合更罕见的算法，当我把它转换成php时，它完美地完成了工作，无需担心重叠或任何事情。

相关内容

最新更新

热门标签：