从集合中选择随机子集的最佳方法？

Question

我在Vector中有一组对象,我想从中选择一个随机子集(例如100个项目返回;随机选择5个).在我的第一次(非常草率)传球中,我做了一个非常简单且可能过于聪明的解决方案:

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

虽然这样做的好处很简单,但我怀疑它不能很好地扩展,即Collections.shuffle()必须至少为O(n).我不太聪明的选择是

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

有关更好地从集合中抽取随机子集的方法的任何建议吗？

Answer 1

Jon Bentley在"Programming Pearls"或"More Programming Pearls"中对此进行了讨论.您需要小心N的M选择过程,但我认为显示的代码可以正常工作.而不是随机洗牌所有项目,你可以做随机洗牌只改组前N个位置 - 当N << M时,这是一个有用的保存.

Knuth还讨论了这些算法 - 我相信这将是第3卷"排序和搜索",但我的设置已经打包等待搬家,所以我无法正式检查.

Answer 2

@Jonathan,

我相信这是你所说的解决方案:

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

它位于Jon Bentley的Programming Pearls的第127页,它基于Knuth的实现.

编辑:我刚看到第129页的进一步修改:

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

这是基于"......我们只需要对阵列的前m个元素进行洗牌......"

Answer 3

如果你试图从 n 的列表中选择 k 个不同的元素，你上面给出的方法将是 O(n) 或 O(kn)，因为从 Vector 中删除一个元素将导致 arraycopy 将所有元素向下移动.

由于您要求的是最佳方式，因此这取决于您可以对输入列表执行的操作。

如果修改输入列表是可以接受的，就像你的例子一样，那么你可以简单地将 k 个随机元素交换到列表的开头，并在 O(k) 时间内返回它们，如下所示：

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

如果列表必须以开始时的状态结束，您可以跟踪您交换的位置，然后在复制您选择的子列表后将列表返回到其原始状态。这仍然是一个 O(k) 解决方案。

但是，如果您根本无法修改输入列表并且 k 远小于 n（例如 100 中的 5），那么最好不要每次都删除所选元素，而只需选择每个元素，如果您得到一个重复的，把它扔掉并重新选择。这会给你 O(kn / (nk)) 当 n 支配 k 时，它仍然接近 O(k)。（例如，如果 k 小于 n / 2，则它减少到 O(k)）。

如果 k 不受 n 支配，并且您无法修改列表，那么您不妨复制您的原始列表，并使用您的第一个解决方案，因为 O(n) 将与 O(k) 一样好。

正如其他人所指出的，如果您依赖强随机性，其中每个子列表都是可能的（并且是无偏见的），那么您肯定需要比java.util.Random. 见java.security.SecureRandom。