Geek asks and answers

Randomly select k bits from n from Java BitSet

How to select exactly a kbit from a Java BitSet length mwith bits included n, where k≤n≤m?

Input Example: m=20, n=11 enter image description here

Output Example: k=3 enter image description here

Naive approach

Choose a random number 0≤ i ≤ m-1. If it is turned on at the input and not turned on at the output, turn it on at the output until the bits are turned on at the output k.

This approach fails when nmuch less than m. Any other ideas?

+3
source share
4 answers

You can scan the set from the first bit to the last and apply the collector jam to the set bits.

O(m) O(k) .

+5

, :

a List, . Collections#shuffle. k .

EDIT. , , k , n . : k , [0, n]. , : 1, , . , - , .

+1

n , k ?

+1

If a nlot more than kthat, you can simply hide the Shuffle Fisher-Yates algorithm to stop after you choose as many as you need:

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;
}
+1
source

More articles:


All Articles