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

algorithm random collections java subset

2022-08-31 14:13:07

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

关于从集合中绘制随机子集的更好方法的任何建议？

答案 1

Jon Bentley在“Programming Pearls”或“More Programming Pearls”中讨论了这个问题。您需要小心选择N of M的过程，但我认为显示的代码可以正常工作。您可以只随机洗牌前N个位置，而不是随机洗牌所有项目 - 当N<<M时，这是一个有用的节省。

Knuth还讨论了这些算法 - 我相信这将是Vol 3“排序和搜索”，但我的集合已经打包等待搬家，所以我无法正式检查。

答案 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的Dgramming 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 个元素...”