对于我正在进行的项目，我需要一种方法来计算具有 type 的数据结构的唯一整数表示[(int, int)]，即（非负）整数对的集合。要求是，虽然对中的顺序很重要，但集合本身是顺序不敏感的。经过一番搜索，我开始相信一个合适的解决方案是使用 Cantor 配对函数和xor结果对每一对进行编码。
范围将相当小，例如对中的第一个整数为 1-700，第二个整数为 1-10，列表将包含大约 5-15 个这些对。
如果您认为有更好的解决方案，请告诉我，但回答“是的，这会奏效”也会很棒:)
问问题
113 次
1 回答
2
[这个答案假设当你说“独特”时，你真的是那个意思；碰撞是不可接受的。]
如果目标是以某种方式将任意大小的整数（对）集合唯一地映射到单个（大小合理）的整数上，那么答案基本上是“不可能的”。这可以通过诉诸鸽巢原理很容易地证明。
如果您的集合的大小非常有限，并且输入整数的范围非常有限，那么您也许可以做一些事情。但在一般情况下，我建议为您的顶级问题寻找不同的解决方案。
更新
作为一个工作示例，让我们考虑您添加到问题中的参数。700 * 10 = 7000，因此您需要大约 13 位来唯一地表示每个可能的对。最多 15 对，总共需要195 位。
现在，如果顺序无关紧要，那么理论上您可以删除 log2(15!) = 40 位。*所以理论上，你需要一个155 位 的输出数据类型。这容易处理吗？
*如何在实践中实现这一点是另一个问题... ;)
于 2013-01-13T18:54:20.613 回答