从N个元素中均匀随机选择M个元素-混淆

Question

我知道有人问过类似的问题，比如

从包含n个元素的向量中随机选择m个元素

从未知长度的序列中随机选择N个项目

但我越看越困惑。

从N个元素中均匀随机地选择M个元素

所以我需要从N个元素中选择M个元素。我还需要使被选中的概率均匀分布于每个元素：M/N

我的直觉是

1. 随机选择一个元素
2. 把它拿出来
3. 对其余元素重复此过程

我猜这个解决方案错了？M所选元素的概率为1/N，1/（N-1）<代码>1/（N-M），而不是M/N，对吗？

一个可能的正确解决方案是

1. 只需对整个N个元素进行洗牌
2. 挑最上面的M个。

但我无法计算每个元素被选中的概率。

有谁能证明这个解决方案的概率确实是M/N？

当然，我们也可以使用储层取样，其概率为M/N。

Answer 1

虽然shuffle方法有效，但还有一种方法不需要修改原始数组。事实上，你甚至不需要知道总共有多少项。你可以从一个流中随机选取M个项目，你唯一需要保存的数据就是这些M个项目的数组。

基本思想是从未知长度的流中挑选单个项目的算法的扩展。同样，你不知道流中有多少项目。所以你总是有一个选定的项目，但是你可能随时改变选定的项目。

首先，没有选定的项目，计数为0。当第一件物品进来时，增加计数。然后在0到count-1之间选择一个随机数。如果该值为0，则将当前项设置为选定项。第一个随机数必须是0，因为你的范围是0到0。

当您读取每个项目时，您增加计数，选择随机数，如果选择的随机数为0，则将当前项目设为选定项目。它看起来像这样：

selected_item = none
count = 0
for each item
    count = count + 1
    if (random(count) == 0)
        selected_item = current_item

这是因为选择当前项目的机会随着每个项目的读取而减少。也就是说，第一个项目被选中的可能性为1/1。当第二个项目进来时，您有1/2的机会选择它来替换第一个项目。当您收到第三个项目时，您有1/3的机会用新项目替换当前选定的项目。

当您到达流的末尾时，您将为每个项目提供平等的被选中机会。

你可以很容易地将它扩展到多个项目。首先，选择第一个进来的M个项目，并将它们放在选定的项目数组中。然后，每当一个新项目进来时，你就选择一个介于0和Count-1之间的随机数，如果这个数字小于M，那么你就随机用新项目替换一个选定的项目。它看起来像这样：

selected_items = array of M items
count = 0
for each item
    if (count < M)
        selected_items[count] = current_item
    else
        if (random(count) < M)
            // pick a random number from 0 to M-1
            // and replace that item with the new item
            ix = random(M)
            selected_items[ix] = current_item

我在我的博客《随机选择》（Random selection）中写了更多关于这方面的细节。

Answer 2

被选取元素的概率：

First: 1/N;
Second: 1/(N-1) * (1 - 1/N) = 1/N
...

其中，（1-1/N）是第二个项目在第一步未被拾取的概率，这是在第二步拾取该项目的条件。这里，1/N是在第一步选择某个元素的概率，（1-1/N）-在第二步选择的元素在第二步可供选择的概率。

Third: 1/(N-2) * (1 - 1/N - 1/N) = 1/N

其中（1-1/N-1/N）是元素在第三步可供选择的概率。

等等。

这里的要点是，对于任何元素，在一个步骤中选择的概率是1/N。

Answer 3

我认为你的困惑可能是你没有区分选择序列和选择集合。

在你的第一个过程中，仅仅因为你在第一轮中只有1/N的机会选择一个特定的元素，并不意味着你不会在接下来的一轮中选择它。该元素有1/N机会成为结果中的第一个元素。。。但它在某一轮中有被选中的机会。这样就行了。假设M=2，N=4：一个元素被选中的几率是1/4（3/4）*（1/3）=2/4。

对于第二个过程，在shuffle之后，每个元素在数组中的位置是均匀分布的，所以它的位置有一个等于或小于M的机会（因此被选择）。所以这也有效。