从stl容器中绘制n个随机元素(无替换)

Question

与this question大致相同，但如果要选择的容器在颗粒中尽可能通用(即只有一个Forward Container，甚至可能只是一个简单的Container)，则不应假设容器有一个.size()，并且遍历两次(一次计算大小，一次获得结果集)是不可接受的。

我有一个解决方案，它比我想要的要复杂一些，并且有更多的依赖项，所以我希望在3-5行的范围内。

Answer 1

我假设“随机元素”指的是均匀分布的元素。

因为你不知道序列的长度，也不能事先计算它，所以你必须逐步构建你的随机序列。因此，让我们这样做，并希望我们使用的所有概率都很好地相加，以便我们最终得到我们最初想要的结果。

我们将分两步完成这项工作。首先，决定绘制哪个序列号，然后如果需要，我们可以为它们选择一个随机顺序(从问题中看不清楚)。我就叫你的N 'K'，因为这对我来说更简单。

首先，我们创建一个K元素数组，用于保存K个绘制的元素。我们遍历序列的前K个元素，并将它们复制到数组中。如果序列没有K个元素，我们说"No can do“。

现在我们知道我们有来自K大小序列的K个随机元素。如果我们在序列的末尾，我们就完成了。如果不是，我们知道我们有一个K+1大小的序列。这里有两个选项，要么选择第K+1个项目，要么不选择。

第K+1个项目被选中的概率是多少？我发现计算第K+1项未被选中的概率更容易。从K+1中选择K个元素有(K+1 over K)方法，如果K+1的元素没有出现，则只有(K over K)方法选择K个元素。因此(K对K) / (K+1对K)是第K+1个项目未被选中的概率。

因此，在0和1之间选择一个随机数，如果它小于1/(K+1)第K+1‘个元素不出现在序列中。如果随机数大于这个数，那么序列中就会出现第K+1‘个元素。在1和K之间选择一个随机元素，并将其替换为第K+1个元素。

现在我们转到下一个项目，第K+2个项目。我们再做一次同样的事情。第K+2‘项不出现在序列中的概率是(K上的K+1)/(K上的K+2)。

这样做，直到序列耗尽。然后你有一个从序列中随机选择的K个元素的列表。

请注意，它们不是随机排序的(至少对于短序列不是这样)，因此您可能希望为此选择一个随机的K大小排列。

免责声明:概率是一条母狗，尽管这在我看来是正确的，但我有可能遗漏了一些东西，最终结果将不会均匀分布。其他人很快就会说出来。