完整的问题是：
编写一个方法，从一个大小为 的数组中随机生成一组 m 个整数
n。每个元素必须具有相同的被选中概率`
这个问题是从“Crack the coding interview”中挑选出来的，解决方案是这样的：
我们可以将元素与数组开头的元素交换，然后“记住”数组现在只包含元素
j和更大的元素。也就是说，当我们选择subset[0]be时array[k]，我们用array[k]数组中的第一个元素替换。当我们选择 时subset[1]，我们认为是“死的”，我们选择1 和 array 之间array[0]的随机元素。然后我们设置子集[1] 等于，并设置等于数组[1]。元素 0 和 1 现在“已死”。现在从 中选择，依此类推。ysize()array[y]array[y]Subset[2]array[2]array[array size()]
我的问题是，如果我们缩小从中选择随机数的数组，那么每个数字被选择的概率1/remaining_num_elements。它如何对所有元素保持相等？
想象一下，就像您m从一袋数字中挑选随机数一样n，第一个j元素表示the numbers in your hand，其余元素表示the numbers still in the bag. （正如你的书所建议的那样，你j从 0迭代到提取数字。然后，代表你已经从袋子中取出的整数的数量。）m - 1j
如果您m在现实生活中从一个袋子中挑选整数，那么每次您选择一个新数字时，您只会从袋子中而不是从您的手中取。因此，remaining_num_elements每一步收缩。
当你这样想的时候，应该很容易看出这种方法保证了每个元素都有相同的被选中的概率。
如果我们缩小从中选择随机数的数组，那么每个数字被选择的概率为 1/remaining_num_elements。
是的，你是对的，但是一个元素在特定回合中被拾取1/remaining_num_elements的概率。在这里，我们对元素最终被轮流拾取的概率感兴趣。对于所有元素，它保持不变。mn
你需要问的问题是：每个n元素是否都有公平和平等m的机会被轮流捡起？答案是肯定的，因为，
P（最终在一组元素中拾取m元素）= P（在第一轮中拾取元素）+
P（在第一轮中未拾取元素）* P（在第二轮中拾取元素）+
P(元素在第 2 回合没有被拾取) * P(元素在第 3 回合被拾取) + ... 等等
n如果您计算，它对于最初存在的所有元素保持不变。
您在概率中看到的差异是由于它是条件属性的事实（事实上已经选择了某些东西并且在最后一次提取中这个元素没有被选择或提取）。但是，选择任何给定球的概率或公平性总体上不会改变。