2つの整数を1つにマッピングする、一意かつ決定論的な方法 質問する

カンターペアリング関数シンプル、高速、省スペースであることを考えると、これは本当に優れたツールの1つですが、Wolframで公開されているものよりも優れたツールがあります。マシュー・ズジック著、こちらカントールペアリング関数の（相対的な）限界は、2N入力が2Nビット整数の場合、エンコードされた結果の範囲が常に1ビット整数の範囲内に収まるとは限らないことです。つまり、入力が16から の範囲の2ビット整数である場合0 to 2^16 -1、2^16 * (2^16 -1)入力の組み合わせが可能であるため、明らかなようにピジョンホール原理、少なくとも のサイズの出力が必要です2^16 * (2^16 -1)。これは に等しく2^32 - 2^16、言い換えると、32ビット数のマップが理想的には実現可能である必要があります。これは、プログラミングの世界では実用上それほど重要ではないかもしれません。

カンターペアリング関数:

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

2 つの最大 16 ビット整数 (65535、65535) のマッピングは 8589803520 になりますが、これは 32 ビットに収まらないことがわかります。

Szudzik 関数を入力します:

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からbの範囲になります0 to 2^15 - 1。

カンターペアリング関数:

2 つの最大 16 ビット符号付き整数 (32767、32767) のマッピングは 2147418112 となり、これは符号付き 32 ビット整数の最大値にわずかに足りません。

さて、Szudzik の機能:

(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;

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;

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

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;
}