java - 从 Java BitSet 中随机选择 n 个比特中的 k 个比特

Question

如何从打开k位的Java BitSet中准确m地选择位，在哪里？nk≤n≤m

示例输入：m=20, n=11

示例输出：k=3

天真的方法

选择一个随机数0≤ i ≤ m-1。如果它在输入上打开而不在输出上打开，则在输出中打开它，直到在输出k中打开位。

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

Answer 1

您可以从第一位扫描到最后一位，并将水库采样应用于设置的位。

该算法具有O(m)时间复杂度，并且需要O(k)内存。

Answer 2

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

构造一个List保存所有设置位的索引。照着做Collections#shuffle。从混洗列表中选择第一个k索引。

编辑k根据评论，如果这个算法真的很小，那么这个算法可能效率很低，而n很大。这是另一种选择：k在区间内生成随机的不同数字[0, n]。如果在生成数字的过程中，该数字已经存在于所选索引的集合中，请执行链接方法：即将该数字增加 1，直到您获得该集合中尚不存在的数字。最后，生成的索引是您在设置位中选择的索引。

Answer 3

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

Answer 4

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