在Java的BitSet中，从n个比特位中随机选择k个比特位。

Question

如何从长度为m的Java BitSet数据中选择恰好k个已打开的位，其中有n个已打开，且k≤n≤m？

例如输入：m=20, n=11 例如输出：k=3

朴素方法

选择一个随机数0≤ i ≤ m-1。如果这个数在输入中被打开并且在输出中未被打开，则打开它，在输出中重复此步骤，直到有k个位在输出中被打开。

当n远小于m时，此方法会失败。还有其他想法吗？

- Adam Matan

Answer 1

你可以从第一个比特位扫描到最后一个，对已设置的比特位应用蓄水池抽样。

该算法的时间复杂度为O(m)，需要O(k)的内存。

- NPE

Answer 2

如果 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;
}

- maybeWeCouldStealAVan

---

内存复杂度是O(n)，对于n非常大而k非常小的情况下效率较低。 - Adam Matan

@AdamMatan 是的，如果你的伪随机数生成器非常快，那么水塘抽样似乎是一个不错的选择，因为你需要调用它 m-k 次。如果不是很快，你可以在 [0..n) 中选择 k 个值，跳过重复项（k/n 约为 0，因此这是有效的），放入排序集合中。然后，在 m 规模上，你唯一需要做的就是计算集合位，并注意每当你的计数在随机值集合中时。获取 n 可能会有问题，因为它需要额外的传递来进行计数。 - maybeWeCouldStealAVan

Answer 3

如果约束条件允许，您可以通过以下方式解决任务：

构建一个包含所有设置位索引的List。对其进行Collections#shuffle操作。从洗牌后的列表中选择前k个索引。

编辑 根据评论，如果k非常小而n很大，则此算法可能效率低下。这里有一种替代方法：在区间[0，n]中生成k个随机且不同的数字。如果在生成数字时该数字已经存在于所选索引集合中，则采用链接方法：即将数字增加1，直到获得尚未出现在集合中的数字。最后，生成的索引是您在设置位中选择的索引之一。

- Boris Strandjev

---

对于小的k和大的n值来说效率低下。 - Adam Matan

@AdamMatan 我不是完全确定。使用随机试探的替代方案可能会在小n的情况下导致无限循环。我的方法的复杂度在内存和时间上都是O(m)。如果你想让算法真正随机，就不能减少时间。对于较小的k，你可能可以减少内存。我将尝试编辑并改进这一点。 - Boris Strandjev

谢谢，鲍里斯 - 内存改进会很棒。 - Adam Matan

Boris，第二种方法并不是随机的，因为它更倾向于稀疏位而不是密集聚类。考虑 000000001000000011111。最左边的位被选中的机会比右侧块中聚集的位要多。 - Adam Matan

@AdamMatan 不，我只考虑设置的位，因此我生成 k 个随机数，最多达到 n，而不是 m。 - Boris Strandjev

Answer 4

首先，如何找到所有集合位的n个位置并将它们放入一个集合中，然后从该集合中随机选择k个位置？

- Victor Sorokin