java - n1のランダムなビットセットを生成します

Question

重複の可能性：
Javaビットセットからnからkビットをランダムに選択します

サイズがn*n（例：64）で正確にn（eq 8）の数の1のランダムなビットセットをランダムな順序で生成する簡単な方法はありますか？

私が考えたのは、ランダムなビットセットを生成し、bitSet.cardinality（）が8であるかどうかを確認し、そうでない場合は再試行できるということですが、これはパフォーマンスの悪い解決策のようです。

誰かもっと良いアイデアがありますか？

Answer 1

リザーバー サンプリングを使用すると、これは O(N) 時間で実行できます。

public static BitSet randomBitSet(int size, int cardinality, Random rnd) {
    if (0 > cardinality || cardinality > size) throw new IllegalArgumentException();
    BitSet result = new BitSet(size);
    int[] chosen = new int[cardinality];
    int i;
    for (i = 0; i < cardinality; ++ i) {
        chosen[i] = i;
        result.set(i);
    }
    for (; i < size; ++ i) {
        int j = rnd.nextInt(i+1);
        if (j < cardinality) {
            result.clear(chosen[j]);
            result.set(i);
            chosen[j] = i;
        }
    }
    return result;
}

Answer 2

0 から 63 までの 8 つの異なる乱数を取得します。これらのビットを 1 に設定します。

あなたのアプローチは正確に8つの1を保証するものではなく、64ビットごとに8つの1の平均値だけです(十分な回数繰り返された場合)。

Answer 3

0 から 63 など、選択したい数字のリストを作成します。

リストをシャッフルします。

n最初のビット、たとえば最初の 8 ビットを 1 に設定します。

これには O(n^2) 時間の複雑さが伴います。

---

別の方法として、BitSet を作成し、合計 8 個を設定するまで、ランダムにクリアされたビットを設定し続けることもできます。カーディナリティをテストする必要はありません。

int n = ...
Random rand = new Random();
BitSet bs = new BitSet(n * n);
for(int i = 0; i < n; i++) {
   int j = rand.nextInt(n * n);
   if (bs.get(j)) 
       i--;
   else
       bs.set(j);
}

これは通常、O(n) よりもわずかに悪い

Answer 4

1. 文字の配列を設定します: {1 1 1 1 1 1 1 0 0 ... 0 0 0} 正確に正しい数の 1 と 0 を使用します。

2. Fisher-Yates アルゴリズムを使用して、文字配列のランダム シャッフルを実行します。

3. シャッフルされた配列を BitSet に変換します。「1」文字が表示される場所では、対応するビットを 0b1 に設定します。他のすべてのビットは 0b0 に設定できます。

ETA: もう少し考えてみると、おそらく BitSet を直接作成してシャッフルすることができます。基礎となるアルゴリズムは同じです。