14

简而言之：如何散列一个免费的多骨牌？

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

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

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

F pentimino

如何在这个 polyomino 上加上一个数字 - 也就是说，散列一个免费的 polyomino？我不想依赖于“命名”多米诺骨牌的预填充列表。无论如何，广泛同意的名称只存在于订单 4 和 5。

这不一定等同于枚举给定顺序的所有自由（或单边，或固定）多骨牌。我只想计算给定配置出现的次数。如果一个生成算法从不产生某个 polyomino，那么它就不会被计算在内。

计数的基本逻辑是：

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 的任何坐标

我真的在寻找新的算法来避免一般蛮力方法所需的整数运算数量的增加，如下所述。

蛮力

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

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

获得每个哈希的操作顺序是：

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

6 回答 6

12

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

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

它确实引入了一个额外的约束：polyomino 不能有完全封闭的洞。（形式上，它必须是简单连接的。）大多数关于多骨牌的讨论都认为存在一个洞，即使它只被两个接触的角密封，因为这可以防止与任何其他非平凡的多骨牌平铺。跟踪边缘不会因接触角而受到阻碍（如在带有孔的单个七合奏中），但它不能像在完整的环形八合奏中那样从一个外环跳到内环：

在此处输入图像描述

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

示例：

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

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

这是顺时针追踪的 F pentomino：

在此处输入图像描述

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 编码，它是：

Base 3 编码的最大位数

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

于 2012-08-18T17:15:08.293 回答
4

您可以将其减少到 8 个哈希操作，而无需翻转、旋转或重新翻译。

请注意，此算法假设您使用相对于自身的坐标进行操作。也就是说，它不在野外。

与其应用翻转、旋转和平移的操作，不如简单地更改散列的顺序。

例如，让我们以上面的 F pent 为例。在这个简单的例子中，让我们假设散列操作是这样的：

int hashPolySingle(Poly p)
    int hash = 0
    for x = 0 to p.width
        fory = 0 to p.height
            hash = hash * 31 + p.contains(x,y) ? 1 : 0
    hashPolySingle = hash

int hashPoly(Poly p)
    int hash = hashPolySingle(p)
    p.rotateClockwise() // assume it translates inside
    hash = hash * 31 + hashPolySingle(p)
    // keep rotating for all 4 oritentations
    p.flip()
    // hash those 4

我不会将该函数应用于多边形的所有 8 个不同方向，而是将 8 个不同的哈希函数应用于 1 个多边形。

int hashPolySingle(Poly p, bool flip, int corner)
    int hash = 0
    int xstart, xstop, ystart, ystop
    bool yfirst
    switch(corner)
        case 1: xstart = 0
                xstop = p.width
                ystart = 0
                ystop = p.height
                yfirst = false
                break
        case 2: xstart = p.width
                xstop = 0
                ystart = 0
                ystop = p.height
                yfirst = true
                break
        case 3: xstart = p.width
                xstop = 0
                ystart = p.height
                ystop = 0
                yfirst = false
                break
        case 4: xstart = 0
                xstop = p.width
                ystart = p.height
                ystop = 0
                yfirst = true
                break
        default: error()
    if(flip) swap(xstart, xstop)
    if(flip) swap(ystart, ystop)

    if(yfirst)
        for y = ystart to ystop
            for x = xstart to xstop
                hash = hash * 31 + p.contains(x,y) ? 1 : 0
    else
        for x = xstart to xstop
            for y = ystart to ystop
                hash = hash * 31 + p.contains(x,y) ? 1 : 0
    hashPolySingle = hash

然后以 8 种不同的方式调用它。您还可以将 hashPolySingle 封装在拐角处的 for 循环中，以及是否围绕翻转。都一样。

int hashPoly(Poly p)
    // approach from each of the 4 corners
    int hash = hashPolySingle(p, false, 1)
    hash = hash * 31 + hashPolySingle(p, false, 2)
    hash = hash * 31 + hashPolySingle(p, false, 3)
    hash = hash * 31 + hashPolySingle(p, false, 4)
    // flip it
    hash = hash * 31 + hashPolySingle(p, true, 1)
    hash = hash * 31 + hashPolySingle(p, true, 2)
    hash = hash * 31 + hashPolySingle(p, true, 3)
    hash = hash * 31 + hashPolySingle(p, true, 4)
    hashPoly = hash

通过这种方式，您隐式地从每个方向旋转多边形，但实际上并没有执行旋转和平移。它执行 8 次散列，这似乎是完全必要的，以便准确地散列所有 8 个方向，但不会浪费在实际上不进行散列的多边形上的传递。在我看来，这似乎是最优雅的解决方案。

请注意，可能有更好的 hashPolySingle() 算法可供使用。我的使用笛卡尔穷举算法，其数量级为O(n^2). 其最坏的情况是 L 形，与 I 形相比，这将导致只有元素的N/2 * (N-1)/2大小为 正方形，或效率为。也可能是架构强加的固有不变性实际上会使其效率低于朴素算法。N1:(N-1)/41:1

我的怀疑是，通过将节点集转换为可以遍历的双向图来模拟笛卡尔耗尽可以缓解上述担忧，从而导致节点以与我更天真的哈希算法相同的顺序被命中，忽略空格。这将使算法下降到O(n)应该能够及时构建图形O(n)。因为我没有做过，所以不能肯定，所以我说这只是一个怀疑，但应该有办法去做。

于 2012-08-17T18:47:45.403 回答
3

这是我的 DFS（深度优先搜索）解释：

从最上面的单元格开始（最左边的作为决胜局）。将其标记为已访问。每次您访问一个单元时，请检查所有四个方向以查找未访问的邻居。始终按此顺序检查四个方向：上、左、下、右。

例子

在此处输入图像描述

在此示例中，up 和 left 失败，但 down 成功。到目前为止，我们的输出是 001，我们递归地搜索“向下”单元格。

我们将新的当前单元格标记为已访问（当我们完成搜索此单元格时，我们将完成对原始单元格的搜索）。这里，上=0，左=1。

我们搜索最左边的单元格，没有未访问的邻居（上 = 0，左 = 0，下 = 0，右 = 0）。到目前为止，我们的总产量是 001010000。

在此处输入图像描述

我们继续搜索第二个单元格。下=0，右=1。我们搜索右侧的单元格。

在此处输入图像描述

上=0，左=0，下=1。搜索向下的单元格：全 0。到目前为止的总输出是 001010000010010000。然后，我们从下行单元返回......

在此处输入图像描述

对=0，返回。返回。（现在，我们在起始单元格。）right=0。完毕！

因此，总输出为 20 (N*4) 位：00101000001001000000。

编码改进

但是，我们可以节省一些位。

最后访问的单元格将始终为其四个方向编码 0000。因此，不要对最后访问的单元格进行编码以节省 4 位。

另一个改进：如果您通过向左移动到达一个单元格，请不要检查右侧的单元格。因此，我们每个单元只需要 3 位，除了第一个单元的 4 位和最后一个单元的 0 位。

第一个单元格永远不会有向上或左侧邻居，因此请忽略这些位。所以第一个单元需要 2 位。

因此，通过这些改进，我们仅使用 N*3-4 位（例如 5 个单元 -> 11 位；9 个单元 -> 23 位）。

如果你真的想要，你可以通过注意恰好 N-1 位将是“1”来压缩更多。

警告

是的，您需要对 polyomino 的所有 8 个旋转/翻转进行编码，并选择最少的以获得规范编码。

我怀疑这仍然会比大纲方法更快。此外，多米诺骨牌上的洞应该不是问题。

于 2012-09-01T00:35:54.387 回答
1

我最近处理了同样的问题。我通过 (1) 为多骨牌生成唯一 ID 相当简单地解决了这个问题，这样每个相同的多骨牌都将具有相同的 UID。例如，找到边界框，对边界框的角进行归一化，收集非空单元格的集合。(2) 通过旋转（和翻转，如果合适的话）polyomino 来生成所有可能的排列，并寻找重复项。

除了简单之外，这种粗略方法的优点在于，如果多边形以其他方式可区分，例如如果其中一些是彩色或编号的，它仍然有效。

于 2012-08-17T17:29:53.993 回答
1

您可以设置类似trie的东西来唯一标识（而不仅仅是散列）您的多米诺骨牌。拿你的归一化多米诺骨牌并建立一个二叉搜索树，其中根分支取决于 (0,0) 是否具有集合像素，下一级分支取决于 (0,1) 是否具有集合像素，依此类推。当你查找一个 polyomino 时，只需对其进行归一化，然后遍历树即可。如果你在 trie 中找到它，那么你就完成了。如果不是，则为该 polyomino 分配一个唯一的 id（只需增加一个计数器），生成所有 8 个可能的旋转和翻转，然后将这 8 个添加到 trie。

在尝试未命中时，您必须生成所有旋转和反射。但是在 trie 命中时，它的成本应该更低（k-polyominos 的 O(k^2)）。

为了使查找更加有效，您可以一次使用几个位并使用更宽的树而不是二叉树。

于 2012-08-17T20:39:18.893 回答
0

一个有效的散列函数，如果你真的害怕散列冲突，就是为坐标创建一个散列函数 x + order * y，然后循环遍历一块的所有坐标，添加 (order ^ i) * hash(coord[ i]) 到片段哈希。这样，您可以保证不会发生任何哈希冲突。

于 2012-08-17T17:28:59.383 回答