algorithm - 特定数组的哈希

Question

我有一个非常特殊的问题，我想有效地解决。

几何体由 V 体积定义，编号从 0 到 V-1。每个体积由不同的表面界定，编号从 0 到 N-1)。

                            Volume | Surfaces
                            --------------------
Geometry A (V=2, N=7):      0      | [0 3 5 6 2] 
                            1      | [5 4 2 1]
                            2      | [4 0 1 3 6]

请注意，表面只会在体积中出现一次。此外，一个表面最多包含一个几何体的 2 个体积。

这里是问题:

我对相同的底层几何体有两种不同的描述，我想找到几何体 A 中的哪个体积对应于几何体 B 中的哪个体积。换句话说，我有相同的 N 个表面，但 V 体积的定义不同。

这是一个几何体 B，它可以对应于上面的几何体 A:

                             Volume | Surfaces
                            --------------------
Geometry B (V=2, N=7):      0      | [1 5 4 2]
                            1      | [3 6 5 0 2] 
                            2      | [0 1 3 6 4]

给定几何体 A 和 B，我希望能够尽可能高效地将几何体 A 的每个体积绑定(bind)到几何体 B 中的相应体积。

A   0  1  2
B   1  0  2

解决方案草案:

按升序或降序对每个表面数组进行排序，而不是按照其表面的字典顺序对每个体积进行排序。通过这种方式可以轻松而稳健地解决问题。

更好的解决方案:

为每个数组计算一个快速、唯一的散列，然后根据该散列对卷进行排序。散列不应取决于数组中表面的顺序。

为什么我认为哈希是一个很好的解决方案？

取 hash(Volume) = min([Surfaces])

这个 hash 最多已经有 1 个碰撞，因为一个 surface 只能出现在 2 个 volume 中!

现在，如果我取 hash(Volume) = min([Surfaces]) + max([Sufaces])*N，我仍然最多有 1 次碰撞，但是当 volume 很多时，概率变得非常小和表面。

Answer 1

如前所述，您的解决方案非常接近您的需求。但是，如果你寻求一个完美的散列函数，你可以使用下面的方法:

suppose p_i is the i-th prime number such that p_0 = 2, p_1 = 3, p_2 = 5, p_3 = 7, p_4 = 11, p_5 = 13, p_6 = 17, p_7 = 19 .... We can define a hash function on x_0, x_1, ..., x_k from an array such that h(x_0, ..., x_k) = p_{x_0} p_{x_1} ... p_{x_k}. Also, for the repeated numbers, we can apply the number of repetition as a power of the p_{x_i}. It means, for example, if x_i is repeated 3 times, the power of p_{x_i} in h would be p_{x_i}^3. if number of repetition of x_i is a_i we will have h(x_0, ..., x_k) = p_{x_0}^{a_0} p_{x_1}^{a_1} ... p_{x_k}^{a_k}.

因此，对于几何 A，我们有:

                    Volume |      Surfaces     | Hash
                    ----------------------------------
  geometry A           0   | [0, 3, 5, 6, 2]   | 2 * 7 * 13 * 17 * 5 = 15470 
                       1   | [5, 4, 2, 1]      | 13 * 11 * 5 * 3 = 2145
                       2   | [4, 0, 1, 3, 6]   | 11 * 2 * 3 * 7 * 17 = 7854

与几何 B 的方法类似。由于此函数为每个数组返回一个唯一值(不关心顺序)，您可以使用对应的哈希值排列表面。如果 N 的值不大，可以使用预先计算好的素数列表。