识别唯一的免费 polyomino(或 polyomino 哈希)的算法

Question

简而言之:如何哈希一个免费的 polyomino？

这可以概括为:如何有效地散列任意二维整数坐标集合，其中一个集合包含唯一的非负整数对，并且当且仅当没有平移、旋转时，一个集合才被认为是唯一的, 或者 flip 可以将它映射到另一组？

对于不耐烦的读者，请注意我完全了解蛮力方法。我正在寻找一种更好的方法——或者一种非常有说服力的证明，证明没有其他方法可以存在。

我正在研究一些不同的算法来生成随机 polyominos .我想测试它们的输出以确定它们的随机性——即给定订单的某些实例是否比其他实例更频繁地生成。从视觉上看，很容易识别自由多联骨牌的不同方向，例如，下面的维基百科插图显示了“F”五联骨牌 (Source) 的所有 8 个方向:

如何在这个 polyomino 上加上一个数字——也就是说，散列一个免费的 polyomino？我不想依赖于“已命名”多联骨牌的预先估计列表。无论如何，只有第 4 和第 5 阶存在广泛认可的名称。

这不一定等同于枚举给定顺序的所有自由(或单边或固定)多项式。我只想计算给定配置出现的次数。如果生成算法永远不会生成特定的多联骨牌，那么它就不会被计算在内。

计数的基本逻辑是:

testcount = 10000 // Arbitrary
order = 6         // Create hexominos in this test
hashcounts = new hashtable
for i = 1 to testcount
    poly = GenerateRandomPolyomino(order)
    hash = PolyHash(poly)
    if hashcounts.contains(hash) then  
        hashcounts[hash]++
    else
        hashcounts[hash] = 1 

我正在寻找的是一种高效的 PolyHash 算法。输入的多联骨牌被简单地定义为一组坐标。 T tetronimo 的一个方向可能是，例如:

[[1,0], [0,1], [1,1], [2,1]]:

 |012
-+---
0| X
1|XXX

您可以假设输入的 polyomino 已经标准化为与 X 轴和 Y 轴对齐并且只有正坐标。正式地，每组:

• 将至少有 1 个 x 值为 0 的坐标
• 将至少有 1 个 y 值为 0 的坐标
• 不会有任何 x < 0 或 y < 0 的坐标

我真的在寻找新的算法来避免下面描述的通用蛮力方法所需的整数运算数量的增加。

蛮力

建议使用暴力解决方案 here和 here包括使用每个坐标作为二进制标志将每个集合散列为无符号整数，并采用所有可能的旋转(在我的例子中是翻转)的最小散列，其中每个旋转/翻转也必须转换为原点。这导致每个输入集总共有 23 次集合操作以获得“免费”哈希:

• 旋转(6 倍)
• 翻转 (1x)
• 翻译 (7x)
• 哈希 (8x)
• 找到计算哈希值的最小值 (1x)

其中获取每个哈希的操作顺序是:

1. 哈希
2. 旋转、平移、散列
3. 旋转、平移、散列
4. 旋转、平移、散列
5. 翻转、翻译、散列
6. 旋转、平移、散列
7. 旋转、平移、散列
8. 旋转、平移、散列

Answer 1

好吧，我想出了一个完全不同的方法。 (还要感谢 corsiKa 提供了一些有用的见解!)不是对正方形进行散列/编码，而是对它们周围的路径进行编码。该路径由在绘制每个单元段之前要执行的一系列“转弯”(包括不转弯)组成。我认为从正方形坐标获取路径的算法超出了这个问题的范围。

这做了一件非常重要的事情:它破坏了我们不需要的所有位置和方向信息。获取翻转对象的路径也很容易:只需反转元素的顺序即可。存储紧凑，因为每个元素只需要 2 位。

它确实引入了一个额外的限制条件:polyomino 不能有完全封闭的洞。 (形式上，它必须是 simply connected。)大多数关于多联骨牌的讨论都认为存在一个洞，即使它仅由两个接触角密封，因为这可以防止与任何其他非平凡的多联骨牌平铺。追踪边缘不会因接触角而受到阻碍(如在带有孔的单个 heptomino 中)，但它不能像在完整的环形 octomino 中那样从一个外环跳到内环:

它还产生了一个额外的挑战:找到编码路径循环的最小顺序。这是因为路径的任何旋转(在字符串旋转的意义上)都是有效的编码。为了始终获得相同编码，我们必须找到路径指令的最小(或最大)旋转。值得庆幸的是，这个问题已经解决了:参见示例 http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation .

示例:

如果我们任意为移动操作分配以下值:

• 不转:1
• 右转:2
• 左转:3

这是顺时针方向的 F 五联骨牌:

F pentomino 的任意初始编码是(从右下角开始):

2,2,3,1,2,2,3,2,2,3,2,1

编码得到的最小旋转是

1,2,2,3,1,2,2,3,2,2,3,2

对于 12 个元素，如果每条指令使用两位，则此循环可以压缩为 24 位，如果指令被编码为 3 的幂，则该循环可以压缩为 19 位。即使使用 2 位元素编码也可以轻松地将其放入单个无符号 32 位整数 0x6B6BAE:

   1- 2- 2- 3- 1- 2- 2- 3- 2- 2- 3- 2
= 01-10-10-11-01-10-10-11-10-10-11-10
= 00000000011010110110101110101110
= 0x006B6BAE

以 3 的最高有效幂开始循环的 base-3 编码是 0x5795F:

    1*3^11 + 2*3^10 + 2*3^9 + 3*3^8 + 1*3^7 + 2*3^6 
  + 2*3^5  + 3*3^4  + 2*3^3 + 2*3^2 + 3*3^1 + 2*3^0
= 0x0005795F

围绕 n 阶多联骨牌的路径中的最大顶点数是 2n + 2。对于 2 位编码，位数是移动次数的两倍，因此所需的最大位数是 4n + 4。对于 base-3 编码，它是:

其中“绞刑架”是天花板功能。因此，任何高达 9 阶的多联骨牌都可以编码为单个 32 位整数。了解这一点后，您可以相应地选择特定于平台的数据结构，以便在给定您要散列的多项式最大顺序的情况下进行最快的散列比较。