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

我在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())));
}

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

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

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

@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个元素进行洗牌......"