java - 生成一个包含 n 个 1 的随机 BitSet

Question

Possible Duplicate:
Randomly pick k bits out of n from a Java BitSet

是否有一种简单的方法来生成大小为 n*n(例如 64)且以随机顺序恰好有 n(例如 8)个 1 的随机 BitSet？

我想到的是，我可以生成一个随机位集并检查 bitSet.cardinality() 是否为 8，如果不是，则重试，但这似乎是一个性能不佳的解决方案。

谁有更好的主意？

Answer 1

使用reservoir sampling ，这可以在 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;
}