ruby - 唯一的两个整数对

Question

可能重复：
以独特且确定的方式将两个整数映射为一个

我正在尝试为两个整数对（Ruby）创建唯一标识符：

f(i1,i2) = f(i2, i1) = some_unique_value

那么， i1+i2, i1*i2, i1^i2 -不是唯一的以及 (i1>i2) 吗？“i1”+“i2”：“i2”+“i1”。

我认为以下解决方案可以：

(i1>i2) ? "i1" + "_" + "i2" : "i2" + "_" + "i1"

但：

我必须将结果保存在数据库中并对其进行索引。所以我更喜欢它是一个整数，并且尽可能小。
Zlib.crc32(f(i1,i2)) 能保证唯一性吗？

谢谢。

升级版：

实际上，我不确定结果必须是整数。也许我可以将其转换为十进制： (i1>i2) ？i1.i2：i2.i1

?

score 6 · Accepted Answer

您要查找的内容称为Pairing function。

以下来自德国维基百科页面的插图清楚地显示了它的工作原理：

在 Ruby 中实现：

def cantor_pairing(n, m)
    (n + m) * (n + m + 1) / 2 + m
end

(0..5).map do |n|
  (0..5).map do |m|
    cantor_pairing(n, m)
  end
end
=> [[ 0,  2,  5,  9, 14, 20],
    [ 1,  4,  8, 13, 19, 26],
    [ 3,  7, 12, 18, 25, 33],
    [ 6, 11, 17, 24, 32, 41],
    [10, 16, 23, 31, 40, 50],
    [15, 22, 30, 39, 49, 60]]

请注意，您需要将此配对的结果存储在一个数据类型中，该数据类型的位数与您的两个输入数字加起来的位数一样多。（如果两个输入数字都是 32 位的，您显然需要 64 位数据类型才能存储所有可能的组合。）

score 2 · Accepted Answer

不，Zlib.crc32(f(i1,i2))对于 i1 和 i2 的所有整数值不是唯一的。

如果 i1 和 i2 也是 32 位数字，那么它们的组合比 CRC32 返回的 32 位数字所能存储的要多得多。

score 2 · Accepted Answer

CRC32 不是唯一的，不适合用作密钥。假设您知道整数的最大值i1和i2：

unique_id = (max_i2+1)*i1 + i2

如果您的整数可以是负数，或者永远不会低于某个正整数，您将需要最大值和最小值：

(max_i2-min_i2+1) * (i1-min_i1) + (i2-min_i2)

这将为您提供识别两个整数的绝对最小数字。

score 1 · Accepted Answer

好吧，当输入是超过 4 个字节的任意二进制字符串时，没有 4 个字节的哈希是唯一的。您的字符串来自高度受限的符号集，因此冲突会更少，但“不，不是唯一的”。

有两种方法可以使用小于两个整数的可能值范围的整数：

拥有一个即使偶尔发生碰撞也能正常工作的系统
检查碰撞并使用某种重新散列

使用 1:1 映射解决问题的明显方法要求您知道其中一个整数的最大值。只需将一个乘以最大值并加上另一个，或者确定两个上限的幂，相应地移动一个值，然后在另一个中进行 OR。无论哪种方式，每一位都是为整数中的一个或另一个保留的。这可能会也可能不会满足您的“尽可能小”的要求。

您的 ###_### 字符串每对都是唯一的；如果您可以将其存储为您获胜的字符串。

score 0 · Accepted Answer

0

这是一个更好、更节省空间的解决方案： . 我的回答在这里

于 2012-12-14T02:36:06.493 回答

ruby - 唯一的两个整数对

5 回答 5

Related

Reference