算法来识别一个独特的自由四角（或四角哈希）(Algorithm to identify a uniq

2019-07-31 01:27发布

站内文章 / 移动开发

88 0

够拽才男人

女 | 书童

私信

简而言之： 如何哈希免费四角？

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

对于心急的读者，请注意，我充分意识到蛮力的办法。我正在寻找一种更好的方式 - 或者一个非常有说服力的证据，证明没有其他办法可以存在。

我工作的一些不同的算法来生成随机polyominos 。我想测试自己的输出，以确定他们是如何随机的 - 即在一个给定的顺序的某些情况下产生的频率高于其他。在视觉上，这是很容易识别的自由四角中的不同方位，例如下列维基百科图显示所有的8个方向的“F”五格骨牌（来源）：

如何将一个用数字来表示这个四角 - 也就是说，哈希自由四角？我不想依赖的“命名” polyominos一个prepolulated名单上。从广义上达成一致的名称只存在订单4和5，无论如何。

这不一定equavalent到枚举给定次序的所有的自由（或单面，或固定）polyominos。我只想计算的时间会出现一个给定的配置数量。如果生成算法从不生成一定四角它根本不会被计数。

计数的基本逻辑是：

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算法。输入polyominos被简单地定义为一组坐标。经t tetronimo的一个方向可能是，例如：

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

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

你可以假设该输入四角都已经被标准化对X轴和Y轴进行排列，并有唯一积极的坐标。在形式上，每个设置：

将具有至少1坐标，其中x值为0
将具有至少1坐标其中y值为0
将不会有任何的坐标，其中x <0或y <0

我真的很为避免一般的蛮力方法需要整数运算的越来越多的新算法，如下所述。

蛮力

蛮力溶液建议这里和这里包括使用每个坐标作为二进制标志散列每个组为一个无符号的整数，并考虑所有可能的旋转的最小散列（在我的情况下翻转），其中每一个旋转/翻转也必须是翻译原点。这导致总共为每个输入设置，以获得“自由”散列23个操作：

旋转（10倍）
翻转（1X）
翻译（7倍）
哈希（8X）
计算哈希查找最小值（1X）

当操作的顺序，以获得每个哈希值是：

哈希
旋转，平移哈希
旋转，平移哈希
旋转，平移哈希
翻转，翻译，哈希
旋转，平移哈希
旋转，平移哈希
旋转，平移哈希

Answer 1:

好吧，我想出了一个完全不同的方法。（同时也感谢corsiKa一些有用的见解！）而不是散列/编码广场， 编码周围的路径 。所述路径由“匝”（不包括转）绘制每个单元段之前执行的序列组成。我认为，从广场的坐标获取路径的算法是这个问题的范围之外。

这确实很重要的事：它会破坏所有的位置和方位信息，这是我们不需要的东西。这也很容易得到翻转对象的路径：您只需反转元素的顺序做。存储是紧凑，因为每个元件仅需要2比特。

它确实引入一个附加约束： 在四角不能有完全封闭的孔 。（正式地，它必须被简单地连接 。）polyominos的大部分讨论考虑，即使它是密封的仅由两个接触角的孔存在，因为这会妨碍平铺与任何其他非平凡的四角。跟踪边缘没有通过触摸角（如在单受阻七格骨牌带有一个孔），但它不能从一个外环飞跃到内一个如在完整环状八格骨牌：

它也产生一个额外的挑战：寻找编码的路径循环的最少订货。这是因为路径（串旋转方向）的任何旋转是有效编码。要总是得到相同的编码，我们必须要找到的路径指示的最小（或最大）的旋转。值得庆幸的是这个问题已经得到解决：例如见http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation 。

例如：

如果我们随意分配以下值的移动操作：

无转：1
右转：2
左转：3

这里是F五格骨牌顺时针追踪：

为F五格骨牌任意初始编码（在右下角开始）：

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个元素，该环可以被包装成如果两个比特每个指令使用或者只有19比特，如果指令被编码为三个权力24位。即使采用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最显著权力循环的开始的基-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 。对于基3编码是：

这里的“绞刑架”是天花板上的功能。因此任何四角高达级别9可以在单个32位整数进行编码。知道了这一点，你可以选择相应的给定你会被散列polyominos的最大阶最快的哈希比较特定于平台的数据结构。

Answer 2:

你可以减少它下降到8个散列操作，无需翻盖，旋转或重新翻译。

请注意，这个算法假定你是相对于自身的坐标操作。也就是说它不是在野外。

相反施加动作是翻转，旋转和平移，而不是简单地改变你哈希的顺序。

例如，让我们以上述被压抑的F。在简单的例子，让我们假设散列操作是这样的：

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在蠢蠢欲动环，和周围的翻转与否。全都一样。

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形，这将导致存在是构成N/2 * (N-1)/2尺寸为仅正方形N元件，或的效率1:(N-1)/4 ，相对于I形这将是1:1 。这也可能是由架构所产生的固有不变实际上使它比天真的算法效率较低。

我怀疑的是，上述担忧可以通过模拟由节点集转换为双向曲线笛卡尔疲惫，可以穿越，造成节点以相同的顺序来打我的更天真的散列算法得到缓解，忽略空的空间。这将使算法下降到O(n)的图形应该能够将建造O(n)时间。因为我没有这样做，我不能肯定地说，这就是为什么我说这只是怀疑，但应该有办法做到这一点。

Answer 3:

Here's my DFS (depth first search) explained:

Start with the top-most cell (left-most as a tiebreaker). Mark it as visited. Every time you visit a cell, check all four directions for unvisited neighbors. Always check the four directions in this order: up, left, down, right.

Example

In this example, up and left fail, but down succeeds. So far our output is 001, and we recursively search the "down" cell.

We mark our new current cell as visited (and we'll finish searching the original cell when we finish searching this cell). Here, up=0, left=1.

We search the left-most cell and there are no unvisted neighbors (up=0, left=0, down=0, right=0). Our total output so far is 001010000.

We continue our search of the second cell. down=0, right=1. We search the cell to the right.

up=0, left=0, down=1. Search the down cell: all 0s. Total output so far is 001010000010010000. Then, we return from the down cell...

right=0, return. return. (Now, we are at the starting cell.) right=0. Done!

So, the total output is 20 (N*4) bits: 00101000001001000000.

Encoding improvement

But, we can save some bits.

The last visited cell will always encode 0000 for its four directions. So, don't encode the last visited cell to save 4 bits.

Another improvement: if you reached a cell by moving left, don't check that cells right-side. So, we only need 3 bits per cell, except 4 bits for the first cell, and 0 for the last cell.

The first cell will never have an up, or left neighbor, so omit these bits. So the first cell takes 2 bits.

So, with these improvements, we use only N*3-4 bits (e.g. 5 cells -> 11 bits; 9 cells -> 23 bits).

If you really want, you can compact a little more by noting that exactly N-1 bits will be "1".

Caveat

Yes, you'll need to encode all 8 rotations/flips of the polyomino and choose the least to get a canonical encoding.

I suspect this will still be faster than the outline approach. Also, holes in the polyomino shouldn't be a problem.

Answer 4:

我最近制作的同样的问题。我解决了这个问题相当简单地通过（1）产生一个唯一的ID为四角，使得每个相同聚将具有相同的UID。例如，查找边框，规范边框的角落，并收集组非空单元格。（2）通过旋转（和翻转，如果合适的话）一个四角产生所有可能的排列，并寻找重复。

这种野蛮的方法的优点，比它的简单性等，是它仍然有效，如果息肉在一些其他的方式区分，例如，如果他们中的一些有色或编号。

Answer 5:

您可以设置有点像特里唯一标识（不只是哈希）的四角。把你归四角，并成立了二叉搜索树，其中在（0,0）是否是根树枝有一组像素，在（0,1）是否有一组像素，等下一级分支机构。当你看到一个四角，简单地规范它，然后在树。如果您在线索找到它，那么你就大功告成了。如果没有，分配一个四角唯一的ID（只是增加一个计数器），生成所有8度可能的旋转和翻转，然后添加这些8线索。

在特里小姐，你就必须生成所有的旋转和反射。但是在特里打它的成本，应以下（K-polyominos O（K ^ 2））。

为了让查找更有效，你可以同时使用几个位和使用范围更广的树来代替二叉树。