java - Javaビットセットからnからkビットをランダムに選択します

Question

ビットがオンになっている長さのJavaBitSetから正確にkビットを選択する方法はどこですか？mnk≤n≤m

入力例：m=20, n=11

出力例：k=3

素朴なアプローチ

乱数を選択し0≤ i ≤ m-1ます。入力がオンになっていて、出力がオンになっていない場合は、出力でkビットがオンになるまで、出力でオンにします。

nが。よりもはるかに小さい場合、このアプローチは失敗しますm。他のアイデアはありますか？

Answer 1

セットを最初のビットから最後のビットまでスキャンし、セットされたビットにリザーバーサンプリングを適用できます。

アルゴリズムにはO(m)時間計算量があり、O(k)メモリが必要です。

Answer 2

制約が許せば、次の方法でタスクを解決できます。

Listすべてのセットビットインデックスを保持するように構築します。それをしてくださいCollections#shuffle。kシャッフルされたリストから最初のインデックスを選択します。

編集コメントによると、このアルゴリズムは、kが本当に小さい場合は非効率的である可能性がありますnが、大きい場合もあります。別の方法は次のとおりです。k区間内で乱数を生成します[0, n]。数値の生成時に、選択したインデックスのセットに数値がすでに存在する場合は、連鎖アプローチを実行します。つまり、セットにまだ存在しない数値が得られるまで、数値を1つ増やします。最後に、生成されるインデックスは、設定されたビットの中から選択したものです。

Answer 3

n最初のステップとして、すべてのセットビットの位置を見つけてコレクションに配置しk、そのコレクションからランダムに位置を選択するのはどうですか？

Answer 4

nがよりもはるかに大きい場合はk、Fisher-Yatesシャッフルアルゴリズムを単純化して、必要な数を選択した後で停止することができます。

private static Random rand = new Random();
public static BitSet chooseBits(BitSet b, int k) {
    int n = b.cardinality();
    int[] indices = new int[n];
    // collect indices:
    for (int i = 0, j = 0; i < n; i++) {
        j=b.nextSetBit(j);
        indices[i] =j++;
    }
    // create returning set:
    BitSet ret = new BitSet(b.size());
    // choose k bits:
    for (int i = 0; i<k; i++) {
        //The first n-i elements are still available.
        //We choose one:
        int pick = rand.nextInt(n-i);
        //We add it to our returning set:
        ret.set(indices[pick]);
        //Then we replace it with the current (n-i)th element
        //so that, when i is incremented, the 
        //first n-i elements are still available:
        indices[pick] = indices[n-i-1];
    }
    return ret;
}