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

Question

完整问题是:

Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen`

这个问题是从“破解编码面试”中挑选出来的，解决方案是这样的:

We can swap the element with an element at the beginning of the array and then “remember” that the array now only includes elements j and greater. That is, when we pick subset[0] to be array[k], we replace array[k] with the first element in the array. When we pick subset[1], we consider array[0] to be “dead” and we pick a random element y between 1 and array size(). We then set subset[1] equal to array[y], and set array[y] equal to array[1]. Elements 0 and 1 are now “dead”. Subset[2] is now chosen from array[2] through array[array size()], and so on.

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

Answer 1

像你在采摘一样思考 m来自一袋 n 的随机数数字，第一个 j表示 the numbers in your hand 的元素其余元素表示 the numbers still in the bag . (您将 j 从 0 迭代到 m - 1 以取出数字，正如您的书所建议的那样。然后， j 表示您已经从包中取出的整数的数量。)

如果您选择 m在现实生活中从袋子里取整数，那么每次你选择一个新数字时，你只从袋子里取，而不是从你的手上取。因此，remaining_num_elements每一步都在收缩。

当你这样想时，应该很容易看出这种方法保证了每个元素被选中的概率相等。