Randomly pick k bits out of n from a Java BitSet
algorithm, java
Solution
You could scan the set from the first bit to the last, and apply reservoir sampling to the bits that are set.
The algorithm has `O(m)` time complexity, and requires `O(k)` memory.
Problem
How to pick exactly `k` bits from a Java BitSet of length `m` with `n` bits turned on, where `k≤n≤m`? Example input: `m=20, n=11` Example output: `k=3` The naive approach Choose a random number `0≤ i ≤ m-1`.if it's turned on on the input and not turned on on the output, turn it on in the output, until `k` bits are turned on in the output. This approach fails when `n` is much smaller than `m`. Any other ideas?