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

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

解决方案

但是，使用随机选择元素的第二种方法听起来不错：

• 我们如何学习在线扑克作弊
• 我们如何学习在线扑克作弊
• 向量已同步。如果可能，请改用ArrayList来提高性能。

可以节省多少费用？因为如果需要将数组重写到新的内存块，那么我们已经在第二个版本中完成了O(5n)操作，而不是之前想要的O(n)。

我们可以创建一个设置为false的布尔数组，然后：

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

如果子集比总大小小很多，则此方法有效。当这些大小彼此接近时(即大小的1/4左右)，在该随机数生成器上会遇到更多的冲突。在这种情况下，我将列出一个较大数组的整数列表，然后将整数列表洗牌，然后从中取出第一个元素，以得到(非冲突的)指标。这样，我们将花费O(n)来构建整数数组，并在混洗中花费另一个O(n)，但是内部的while Checker不会产生冲突，并且消除的潜在O(5n)可能要花费。

我个人选择初始实施方式：非常简洁。性能测试将显示其扩展能力。我已经以一种体面的滥用方法实现了一个非常相似的代码块，并且其规模得到了充分的扩展。特定代码还依赖于包含> 10,000个项目的数组。

乔恩·本特利(Jon Bentley)在"编程珍珠"或者"更多编程珍珠"中对此进行了讨论。我们需要谨慎对待N个M个选择过程，但是我认为显示的代码可以正常工作。我们可以只对前N个位置进行混洗，而不是对所有项目进行随机混洗，这在N << M时非常有用。

Knuth还讨论了这些算法，我相信这将是第3卷"排序和搜索"，但是我的场景已经打包好等待搬家了，所以我无法正式对其进行检查。

@乔纳森

我相信这是我们正在谈论的解决方案：

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

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

几周前，我写了一个有效的实现方法。它在C语言中，但是到Java的翻译是微不足道的(基本上是相同的代码)。好的一面是，它也完全没有偏见(有些现有答案不是)，可以在这里进行测试。

它基于Fisher-Yates随机播放的Durstenfeld实现。

如果我们尝试从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 /(n-k))，当n主导k时，该值仍接近O(k)。 (例如，如果k小于n / 2，则它减小为O(k))。

如果k不由n决定，并且我们不能修改列表，则最好复制原始列表并使用第一个解决方案，因为O(n)与O(k)一样好。

正如其他人指出的那样，如果我们依赖于每个子列表都可能存在(且无偏见)的强随机性，那么我们肯定需要比java.util.Random更强的东西。参见java.security.SecureRandom。

这是关于stackoverflow的非常相似的问题。

总结一下该页面上我最喜欢的答案(用户Kyle给出的最答案)：

• O(n)解决方案：遍历列表，并以概率(#needed / #remaining)复制出一个元素(或者对其的引用)。示例：如果k = 5且n = 100，则采用概率5/100的第一个元素。如果复制该副本，则选择概率为4/99的下一个副本；但是如果我们不参加第一个，则概率为5/99.
• O(k log k)或者O(k2)：通过随机选择一个数字<n，然后随机选择一个数字<，建立k个索引的排序列表({0，1，...，n-1}中的数字) n-1等。在每个步骤中，我们需要重新选择选择以避免冲突并保持概率不变。例如，如果k = 5且n = 100，并且第一个选择是43，则下一个选择是在[0，98]范围内，并且如果> = 43，则将其加1. 因此，如果第二个选择是50，则将其加1，然后得到{43，51}。如果下一个选择是51，则将其加2得到{43，51，53}。

这是一些伪python-

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

我是说时间复杂度是O(k2)或者O(k log k)，因为它取决于我们搜索和插入容器中的s的速度。如果s是一个普通列表，则这些操作之一是线性的，则得到k ^ 2. 但是，如果我们愿意将s构建为平衡的二叉树，则可以节省O(k log k)时间。