256個の数字のリスト(0-255)を指定すると、そのリストから128個の数字のサブセットを表現したいと思います。すべての数字はユニークで繰り返されません。バイナリでサブセットを表現する
このサブセットを表現する最もコンパクトな方法は何ですか?
私がこれまで考え出してきたのは、256の長さのビット配列を持ち、適切なインデックスを1に設定していることです。このメソッドは、明らかに128の値を表すのに256ビット必要ですが、方法?
ありがとうございます!
256個の数字のリスト(0-255)を指定すると、そのリストから128個の数字のサブセットを表現したいと思います。すべての数字はユニークで繰り返されません。バイナリでサブセットを表現する
このサブセットを表現する最もコンパクトな方法は何ですか?
私がこれまで考え出してきたのは、256の長さのビット配列を持ち、適切なインデックスを1に設定していることです。このメソッドは、明らかに128の値を表すのに256ビット必要ですが、方法?
ありがとうございます!
256があります。 /(128!*(256 - 128)!)は、256個のアイテムのセットから128個の要素を一意に組み合わせたもので、順序は関係ありません(組み合わせについてはwikiを参照)。
この数値を計算してベース2の対数をとると、それは251.6です。つまり、256のうち128個のアイテムのユニークな選択を表すには、少なくとも252ビットが必要です。.NETはとにかくビット(全バイトのみ)を表すことができないので、実際にこれをどうやって行うことができるのかは実際には分かりません。
128は、この点で最悪の数字です。あなたが5要素を選択した場合、256のうち251を選択した場合、それは34ビットで表現されている可能性があり、そのような種類の効果的な表現を試してみると便利でした。
サブセットの順序は気にしませんし、各要素を元の配列の元の位置に戻すことも気にしないので、これは配列のランダムなサブセットを生成する場合に過ぎません。デッキからカードを引く。
配列からユニークな要素を取るために、あなたは、単にソース配列をシャッフルしてから最初のXインデックスで要素の数をとることができます。
int[] srcArray = Enumerable.Range(0, 256).ToArray();
Random r = new Random();
var subset = srcArray.OrderBy(i => r.Next()).Take(128).ToArray();
注:私は維持するために上記のランダム化方式を使用例は簡潔です。より堅牢なシャッフルアプローチのために、私はthis postで説明されているようにFisher-Yatesアルゴリズムを推奨します。
選択した数字の間には関係がありますか? – xtofl
@xtofl - いいえ128番号が256番号リストの要素であること以外には関係がありません – Kozzy
任意の部分集合を表現しようとしていますか、それともインデックスを決定する方法がありますか? – Abion47