从Java BitSet中随机选取n个k位

如何从n位开启的长度为m的Java BitSet中精确选取k位，其中k≤n≤m ？

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

输出示例： k=3

天真的做法

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

构造一个包含所有设置位索引的List 。 Collections#shuffle就可以了。 从随机列表中选择前k索引。

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

Answer 4

如果n比k大得多，你可以在选择尽可能多的算法后减去Fisher-Yates shuffle算法：

 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