2 つの正の整数 A と B を想像してください。これら 2 つを 1 つの整数 C に結合したいと考えています。
C に結合する他の整数 D と E は存在しません。したがって、これらを加算演算子で結合しても機能しません。例: 30 + 10 = 40 = 40 + 0 = 39 + 1 連結も機能しません。例: "31" + "2" = 312 = "3" + "12"
この組み合わせ演算も決定論的である必要があり (常に同じ入力で同じ結果が得られる) 、常に整数の正または負の側で整数を生成する必要があります。
Cantorペアリング関数は、シンプルで高速でスペース効率が良いことを考えると、実際には優れた関数の1つですが、WolframでMatthew Szudzikによって公開されているさらに優れた関数があります。2NCantor ペアリング関数の (相対的な) 制限は、入力が 2 ビット整数の場合、エンコードされた結果の範囲が常にビット整数の制限内に留まらないことNです。つまり、私の入力が16からの範囲の 2 ビット整数である場合、可能な入力の組み合わせ0 to 2^16 -1が2^16 * (2^16 -1)あるため、明白なピジョンホールの原理により、少なくとも2^16 * (2^16 -1)に等しいサイズの出力が必要です。2^32 - 2^16つまり、 のマップです。32ビット数は理想的には実行可能でなければなりません。これは、プログラミングの世界では実際にはほとんど重要ではないかもしれません。
Cantor ペアリング機能:
(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。
Cantor ペアリング機能:
2 つの最大 16 ビット符号付き整数 (32767、32767) のマッピングは 2147418112 になり、符号付き 32 ビット整数の最大値をわずかに下回ります。
今シュジクの関数：
(32767, 32767) => 1073741823、はるかに小さい..
負の整数を考慮しましょう。それは私が知っている元の質問を超えていますが、将来の訪問者を助けるために詳しく説明しています.
Cantor ペアリング機能:
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 の場合、次のようにすることができます。
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入力に の重みを適用し、関数を実行した後、出力を 2 で割り、それらの一部を で乗算して負の軸にし-1ます。
結果を参照してください。符号付き16ビット数の範囲内の入力に対して、出力は符号付き32ビット整数の制限内にあります。これはクールです。Cantor のペアリング機能についても同じようにする方法はわかりませんが、それほど効率的ではないため、あまり試していません。さらに、カントールのペアリング関数に含まれる計算が増えるということは、その速度も遅くなることを意味します。
これが 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)。
代替ソリューションで提供したリンクは、空間内のすべての点を利用した関数のグラフをうまく表しています。1 組の座標を 1 つの数値に可逆的に一意にエンコードできることは驚くべきことです。数字の魔法の世界!!
NxN -> Nあなたは全単射写像を探しています。これらは、アリ継ぎなどに使用されます。いわゆるペアリング機能の紹介については、この PDFをご覧ください。ウィキペディアでは、特定のペアリング関数、つまりCantor ペアリング関数を紹介しています。
3 つの注意事項:
ZxZ -> Nあなたは全単射写像を探しています。カントールの関数は、非負の数でのみ機能します。f : Z -> Nただし、次のよう
に全単射を定義するのは簡単なので、これは問題ではありません。A と B が 2 バイトで表現できる場合は、4 バイトで結合できます。A を最上位半分に、B を最下位半分に置きます。
C 言語では、次のようになります (sizeof(short)=2 および sizeof(int)=4 と仮定):
int combine(short A, short B)
{
return A<<16 | B;
}
short getA(int C)
{
return C>>16;
}
short getB(int C)
{
return C & 0xFFFF;
}
これは可能ですか？
2 つの整数を結合しています。どちらも -2,147,483,648 から 2,147,483,647 の範囲ですが、正の値のみを取得します。2147483647^2 = 4,61169E+18通りの組み合わせになります。各組み合わせは一意である必要があり、結果が整数になるため、この量の数値を含むことができる何らかの魔法の整数が必要になります。
それとも私の論理に欠陥がありますか？
numberaを最初、b2 番目にします。を- 番目の素数とpする、- 番目の素数とするa+1qb+1
次に、結果はpq、 ifa<b,または2pqifa>bです。ならa=b、そうしましょうp^2。
正の整数の標準的な数学的方法は、素因数分解の一意性を使用することです。
f( x, y ) -> 2^x * 3^y
欠点は、イメージが非常に広い範囲の整数に及ぶ傾向があることです。そのため、コンピューター アルゴリズムでマッピングを表現する場合、結果に適切なタイプを選択する際に問題が発生する可能性があります。
これを変更して、負の値を処理しx、y5 と 7 のべき乗でフラグをエンコードすることができます。
例えば
f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
Stephan202 の答えは唯一の真に一般的なものですが、境界のある範囲内の整数の場合は、より適切に行うことができます。たとえば、範囲が 0..10,000 の場合、次のことができます。
#define RANGE_MIN 0
#define RANGE_MAX 10000
unsigned int merge(unsigned int x, unsigned int y)
{
return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}
void split(unsigned int v, unsigned int &x, unsigned int &y)
{
x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}
結果は、整数型の基数の平方根までの範囲の単一の整数に収まります。これは、Stephan202 のより一般的な方法よりもわずかに効率的にパックされます。また、デコードもかなり簡単です。手始めに、平方根を必要としません:)
f(a, b) = s(a+b) + a、 どこs(n) = n*(n+1)/2
s(a+b+1)-s(a+b) = a+b+1
< a。 私はあなたが何を意味するのか理解できませんでした:
整数の正または負の側で常に整数を生成する必要があります
このフォーラムで (より大きい)、(より小さい) 文字を書くにはどうすればよいですか?
マッピングを作成するのはそれほど難しくありません:
1 2 3 4 5 (a,b) != (b,a) の場合、このマッピングを使用します
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40
1 2 3 4 5 (a,b) == (b,a) (ミラー) の場合、このマッピングを使用します。
1 0 1 2 4 6
2 1 3 5 7 10
3 2 5 8 11 14
4 4 8 11 15 19
5 6 10 14 19 24
0 1 -1 2 -2 負/正が必要な場合はこれを使用します
0 0 1 2 4 6
1 1 3 5 7 10
-1 2 5 8 11 14
2 4 8 11 15 19
-2 6 10 14 19 24
任意の a,b の値を取得する方法を理解することは、もう少し困難です。
これを確認してください: http://en.wikipedia.org/wiki/Pigeonhole_principle . A、B、C が同じ型の場合は実行できません。A と B が 16 ビットの整数で、C が 32 ビットの場合、単純にシフトを使用できます。
ハッシュ アルゴリズムの本質は、異なる入力ごとに一意のハッシュを提供できないことです。
引数が正の整数で、引数の順序が重要でない場合:
順序付けられていないペアリング関数は次のとおりです。
<x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>
x ≠ y の場合、一意の順序付けられていないペアリング関数は次のとおりです。
<x, y> = if x < y:
x * (y - 1) + trunc((y - x - 2)^2 / 4)
if x > y:
(x - 1) * y + trunc((x - y - 2)^2 / 4)
= <y, x>
これは、@nawfal によって指定された方法に基づいて、@DoctorJ のコードを無制限の整数に拡張したものです。エンコードおよびデコードできます。通常の配列とnumpy配列で動作します。
#!/usr/bin/env python
from numbers import Integral
def tuple_to_int(tup):
""":Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
if len(tup) == 0: # normally do if not tup, but doesn't work with np
raise ValueError('Cannot encode empty tuple')
if len(tup) == 1:
x = tup[0]
if not isinstance(x, Integral):
raise ValueError('Can only encode integers')
return x
elif len(tup) == 2:
# print("len=2")
x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2]) # Just to validate x and y
X = 2 * x if x >= 0 else -2 * x - 1 # map x to positive integers
Y = 2 * y if y >= 0 else -2 * y - 1 # map y to positive integers
Z = (X * X + X + Y) if X >= Y else (X + Y * Y) # encode
# Map evens onto positives
if (x >= 0 and y >= 0):
return Z // 2
elif (x < 0 and y >= 0 and X >= Y):
return Z // 2
elif (x < 0 and y < 0 and X < Y):
return Z // 2
# Map odds onto negative
else:
return (-Z - 1) // 2
else:
return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:])) # ***speed up tuple(tup[2:])?***
def int_to_tuple(num, size=2):
""":Return: the unique tuple of length `size` that encodes to `num`."""
if not isinstance(num, Integral):
raise ValueError('Can only encode integers (got {})'.format(num))
if not isinstance(size, Integral) or size < 1:
raise ValueError('Tuple is the wrong size ({})'.format(size))
if size == 1:
return (num,)
elif size == 2:
# Mapping onto positive integers
Z = -2 * num - 1 if num < 0 else 2 * num
# Reversing Pairing
s = isqrt(Z)
if Z - s * s < s:
X, Y = Z - s * s, s
else:
X, Y = s, Z - s * s - s
# Undoing mappint to positive integers
x = (X + 1) // -2 if X % 2 else X // 2 # True if X not divisible by 2
y = (Y + 1) // -2 if Y % 2 else Y // 2 # True if Y not divisible by 2
return x, y
else:
x, y = int_to_tuple(num, 2)
return int_to_tuple(x, size - 1) + (y,)
def isqrt(n):
"""":Return: the largest integer x for which x * x does not exceed n."""
# Newton's method, via http://stackoverflow.com/a/15391420
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
2 つの数値 B と C があり、それらを単一の数値 A にエンコードします。
A = B + C * N
どこ
B=A % N = B
C=A / N = C
あなたが提案することは不可能です。常に衝突が発生します。
2つのオブジェクトを別の単一のセットにマップするには、マップされたセットに、予想される組み合わせの数の最小サイズが必要です。
32ビット整数を想定すると、2147483647の正の整数があります。順序が重要ではなく、繰り返しでこれらの2つを選択すると、2305843008139952128の組み合わせが得られます。これは、32ビット整数のセットにはうまく適合しません。
ただし、このマッピングを61ビットに収めることができます。64ビット整数を使用するのがおそらく最も簡単です。上位の単語を小さい整数に設定し、下位の単語を大きい整数に設定します。
O(1) 空間と O(N) 時間で 2 つの数値を 1 つにエンコードできます。たとえば、0 ～ 9 の範囲の数値を 1 つにエンコードするとします。5 と 6. やり方は？単純、
5*10 + 6 = 56.
5 can be obtained by doing 56/10
6 can be obtained by doing 56%10.
2 桁の整数の場合でも、56 と 45、56*100 + 45 = 5645 としましょう。5645/100 と 5645%100 を実行することで、個々の数値を再度取得できます。
ただし、サイズ n の配列の場合。a = {4,0,2,1,3}、3 と 4 をエンコードするとします。
3 * 5 + 4 = 19 OR 3 + 5 * 4 = 23
3 :- 19 / 5 = 3 3 :- 23 % 5 = 3
4 :- 19 % 5 = 4 4 :- 23 / 5 = 4
それを一般化すると、
x * n + y OR x + n * y
しかし、変更した値にも注意する必要があります。したがって、最終的には次のようになります
(x%n)*n + y OR x + n*(y%n)
得られた数の mod を割って求めることにより、各数を個別に取得できます。