1

私が取り組んでいるプロジェクトの場合、タイプを持つデータ構造の一意の整数表現[(int, int)]、つまり(非負の)整数ペアのコレクションを計算する方法が必要です。要件は、ペア内の順序は重要ですが、コレクション自体は順序に依存しないことです。いくつか検索した結果、適切な解決策は、Cantorの対関数とxor結果を使用して各ペアをエンコードすることであると思いました。

範囲はかなり小さくなります。たとえば、ペアの最初の整数の場合は1〜700、2番目の整数の場合は1〜10で、リストにはこれらのペアの約5〜15が含まれます。

より良い解決策があると思われる場合は、私に知らせてください。ただし、「はい、これでうまくいきます」という答えも素晴らしいでしょう:)

4

1 に答える 1

2

[この回答は、「ユニーク」と言うとき、それが本当に意味することを前提としています。衝突は容認できません。]

任意のサイズの整数 (ペア) のコレクションを単一の (妥当なサイズの) 整数に何らかの方法で一意にマップすることが目的である場合、答えは基本的に「それは不可能です」です。これは、ピジョンホールの原理に訴えることで簡単に実証できます。

コレクションのサイズが非常に限られており、入力整数の範囲が非常に限られている場合は、何かできることがあります。しかし、一般的なケースでは、最上位の問題が何であれ、別の解決策を探すことをお勧めします。


アップデート

実際の例として、質問に追加したパラメーターを考えてみましょう。700 * 10 = 7000 であるため、考えられる各ペアを一意に表すには、約 13 ビットが必要です。最大 15 ペアで、合計で195 ビットが必要です。

ここで、順序が重要でない場合、理論的には log2(15!) = 40 ビットをドロップできます。*したがって、理論的には、 155 ビット の出力データ型が必要です。それは扱いやすいですか?


* 実際にこれをどのように達成するかは別の問題です... ;)

于 2013-01-13T18:54:20.613 に答える