从大小为n的数组中随机生成m个整数集合。

Question

完整问题是：

编写一个方法，从大小为n的数组中随机生成一组m个整数。每个元素被选择的概率相等。

这个问题来自于“Crack the coding interview”，解决方案如下：

我们可以将元素与数组开头的元素交换，然后“记住”现在数组只包括大于j的元素。也就是说，当我们将subset[0]设置为array[k]时，我们将array[k]替换为数组中的第一个元素。当我们选择subset[1]时，我们认为array[0]已经“死亡”，然后我们在1和数组size()之间选择一个随机元素y。然后我们将subset[1]设置为array[y]，并将array[y]设置为array[1]。现在元素0和1已经“死亡”。Subset[2]现在从array[2]到array[array size()]中选择，以此类推。

我的问题是，如果我们正在缩小我们随机选取数字的数组，那么每个数字被选中的概率为1/remaining_num_elements。那么它如何保持所有元素的概率相等？

- studying algorithms

---

请注意，该书的后续版本中解释已经发生了变化。第六版的解释在这里给出。 - Abhijit Sarkar

Answer 1

将它想象成从一个包含n个数字的袋子中随机选取m个数字，其中前j个元素代表手中的数字，剩余的元素代表仍在袋子里的数字。 (你按照书上的建议从0到m-1迭代j来取出数字。因此，j表示你已经从袋子中取出的整数数量。)

如果你在现实生活中从袋子里选择m个整数，每次选择新数字时，都只从袋子里拿，而不是从手中的数字中拿。因此，remaining_num_elements每步都会减少。

这种方法保证了每个元素被选中的概率相等，思考时应该很简单明了。

- irrelephant

Answer 2

如果我们从一个数组中随机选择数字，而这个数组正在缩小，那么每个数字被选中的概率为1/剩余元素数。 是的，你说得对，但是1/remaining_num_elements是一个元素在特定轮次中被选中的概率。在这里，我们感兴趣的是一个元素最终在m轮中被选中的概率，对于所有n个元素来说这个概率是相同的。 你需要问的问题是：在m轮中，每个n个元素是否都有公平和平等的机会被选中？ 答案是肯定的，因为： P（一个元素最终被选择在一组m个元素中）= P（元素在第一轮被选中）+ P（元素在第一轮未被选中）* P（元素在第二轮被选中）+ P（元素在前两轮中未被选中）* P（元素在第三轮被选中）+……等等 如果你计算，它对于所有最初存在的n个元素是相同的。

- srbhkmr

Answer 3

你看到的概率差异是由于条件属性造成的（事实上已经选择了某些元素，在最后一次抽取中该元素未被选中或抽取过）。然而，总体上选择任何给定球的公平性并不会改变。

- Mukul Jain