康托配对功能 http://en.wikipedia.org/wiki/Cantor_pairing_function考虑到它的简单、快速和空间效率，它确实是最好的之一，但 Wolfram 上发布了更好的东西作者：Matthew Szudzik，这里 http://szudzik.com/ElegantPairing.pdf。康托配对函数（相对）的局限性是编码结果的范围并不总是保持在2N位整数（如果输入是两个）N位整数。也就是说，如果我的输入是两个16位整数范围为0 to 2^16 -1，那么有2^16 * (2^16 -1)可能的输入组合，因此显而易见鸽巢原理 http://en.wikipedia.org/wiki/Pigeonhole_principle，我们至少需要一个大小的输出2^16 * (2^16 -1)，等于2^32 - 2^16，或者换句话说，一张地图32理想情况下位数应该是可行的。这在编程世界中可能具有不小的实际重要性。
康托配对功能:
(a + b) * (a + b + 1) / 2 + a; where a, b >= 0
两个最大 16 位整数（65535、65535）的映射将为 8589803520，如您所见，它无法适合 32 位。
Enter 苏兹克函数:
a >= b ? a * a + a + b : a + b * b; where a, b >= 0
(65535, 65535) 的映射现在将为 4294967295，如您所见，这是一个 32 位（0 到 2^32 -1）整数。这就是该解决方案的理想之处，它只是利用该空间中的每个点，因此没有什么可以提高空间效率。
现在考虑到我们通常在语言/框架中处理不同大小的数字的签名实现，让我们考虑一下signed 16位整数范围为-(2^15) to 2^15 -1（稍后我们将看到如何将输出扩展到有符号范围）。自从a and b必须是积极的，它们的范围是0 to 2^15 - 1.
康托配对功能:
两个最大 16 位有符号整数 (32767, 32767) 的映射将为 2147418112，这刚好低于有符号 32 位整数的最大值。
Now 苏兹克函数:
(32767, 32767) => 1073741823，小得多..
让我们考虑负整数。这超出了我知道的最初问题，但只是为了帮助未来的访客而详细阐述。
康托配对功能:
A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;
(-32768, -32768) => 8589803520，即 Int64。 16 位输入的 64 位输出可能是如此不可原谅！
苏兹克函数:
A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;
(-32768, -32768) => 4294967295，对于无符号范围是 32 位，对于有符号范围是 64 位，但仍然更好。
现在，输出始终为正。在签名的世界里，如果我们可以将一半的输出转移到负轴，会更节省空间。对于 Szudzik's，你可以这样做：
A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
(-32768, 32767) => -2147483648
(32767, -32768) => -2147450880
(0, 0) => 0
(32767, 32767) => 2147418112
(-32768, -32768) => 2147483647
我做什么：施加重量后2到输入并遍历该函数，然后我将输出除以二，并将其中一些乘以负轴-1.
查看结果，对于有符号范围内的任何输入16位编号，输出位于有符号的限制内32位整数，这很酷。我不确定如何以相同的方式实现康托配对功能，但没有尝试太多，因为它效率不高。此外，康托配对函数涉及更多计算，意味着其速度也较慢.
这是一个 C# 实现。
public static long PerfectlyHashThem(int a, int b)
{
var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}
public static int PerfectlyHashThem(short a, short b)
{
var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}
由于中间计算可能超出限制2N有符号整数，我用过4N整数类型（最后除以2将结果返回到2N).
我在替代解决方案上提供的链接很好地描述了利用空间中每个点的函数图。令人惊奇的是，您可以将一对坐标可逆地唯一编码为单个数字！神奇的数字世界！！
