1. ホーム

[解決済み】2つの整数を1つにマッピングする、一意的かつ決定論的な方法

2022-04-04 03:37:06

質問

2つの正の整数A、Bがあるとする。この2つを組み合わせて1つの整数Cにしたい。

Cに結合する他の整数DとEは存在し得ない。 だから、加算演算子で組み合わせてもうまくいかない。例:30 + 10 = 40 = 40 + 0 = 39 + 1 連結もうまくいきません。例:"31" + "2" = 312 = "3" + "12"

この組み合わせ操作は、決定論的であるべきです(同じ入力で常に同じ結果を得る)。 そして は常に整数の正負どちらかの側で整数を生成する必要があります。

どのように解くのですか?

あなたは、双対的な NxN -> N マッピングを使用します。これらは、例えば、次のような場合に使用されます。 蟻継ぎ . をご覧ください。 本PDF の紹介は、いわゆる ペアリングファンクション . ウィキペディアでは、特定のペアリング関数、すなわち カントールペアリング関数 :

3つの発言

  • 他の方が明らかにしているように、ペアリング関数を実装するつもりなら、すぐに任意の大きさの整数(ビグナム)が必要だと分かるかもしれません。
  • (a,b)と(b,a)のペアを区別したくない場合は、ペアリング関数を適用する前に、aとbをソートしてください。
  • 実は、私は嘘をつきました。あなたが探しているのは双対的な ZxZ -> N マッピングを使用します。カントールの関数は非負の数に対してのみ有効です。しかし、これは問題ではありません。というのも、双対射を定義するのは簡単だからです。 f : Z -> N というように。
    • f(n) = n * 2 if n >= 0
    • f(n) = -n * 2 - 1 if n < 0