stu*_*hms 5 random probability
完整的问题是:
编写一个方法,从一个大小的数组中随机生成一组m个整数
n.每个元素必须具有相同的被选择概率
这个问题来自"破解编码面试",解决方法是:
我们可以将元素与数组开头的元素交换,然后"记住"数组现在只包含元素
j和更大元素.也就是说,当我们挑选subset[0]是array[k],我们替换array[k]与阵列中的第一个元素.当我们选择时subset[1],我们认为array[0]是"死",我们选择y1和数组之间的随机元素size().然后我们将子集[1]array[y]设置为array[y]等于,并设置为等于array [1].元素0和1现在"死".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 - 1提取数字。j，然后 代表您已经从袋子中提取的整数的数量。）
如果你m在现实生活中从袋子里取出整数，那么每次你取出一个新的数字时，你只是从袋子里取出，而不是从你的手中取出。因此，remaining_num_elements每一步都会收缩。
当你这样想时，应该很容易看出这个方法保证了每个元素被选择的概率相等。