java - 生成具有 n 个 1 的随机 BitSet

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为 1，例如前 8 位。

这将具有 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 1 0 0 ... 0 0 0} 具有正确数量的 1 和 0。

2. 使用 Fisher-Yates 算法对字符数组进行随机洗牌。

3. 将混洗后的数组转换为 BitSet。每当出现“1”字符时，将相应位设置为 0b1。所有其他位都可以设置为 0b0。

ETA：再想一想，您可能可以直接创建和洗牌 BitSet。底层算法还是一样的。