从大小为n的数组中随机生成一组m个整数 [英] Randomly generate a set of m integers from an array of size n
问题描述
完整的问题是:
编写一种方法,从大小为
n
的数组中随机生成一组m个整数.每个元素的选择概率必须相等.
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`
此问题摘自破解编程访谈",而解决方案是:
This question is picked from "Crack the coding interview" and the solution is this:
我们可以在数组的开头将元素替换为元素,然后记住"该数组现在仅包含元素
j
和更大的元素.也就是说,当我们选择subset[0]
为array[k]
时,我们将array[k]
替换为数组中的第一个元素.当我们选择subset[1]
时,我们认为array[0]
是死"的,并且我们选择了一个介于1和数组size()
之间的随机元素y
.然后,将subset [1]设置为等于array[y]
,并将array[y]
设置为等于array [1].元素0和1现在为死".现在从array[2]
到array[array size()]
中选择Subset[2]
,依此类推.
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 picksubset[0]
to bearray[k]
, we replacearray[k]
with the first element in the array. When we picksubset[1]
, we considerarray[0]
to be "dead" and we pick a random elementy
between 1 and arraysize()
. We then set subset[1] equal toarray[y]
, and setarray[y]
equal to array[1]. Elements 0 and 1 are now "dead".Subset[2]
is now chosen fromarray[2]
througharray[array size()]
, and so on.
我的问题是,如果我们要缩小从中挑选随机数的数组,那么每个数字被挑选的概率就会1/remaining_num_elements
.它如何在所有元素上保持相等?
My question is that if we're shrinking the array from which we're picking random numbers then probability of each number being picked 1/remaining_num_elements
. How does it stay equal for all the elements?
推荐答案
想一想,就像您从一包n
数字中选取m
随机数字一样,其中第一个j
元素代表the numbers in your hand
其余元素表示the numbers still in the bag
. (按照书中的建议,您将j
从0迭代到m - 1
以取出数字.j
然后代表您已经从袋子中取出的整数的数量.)
Think about it like you're picking m
random numbers from a bag of n
numbers, with the first j
elements representing the numbers in your hand
and the remaining elements representing the numbers still in the bag
. (You iterate j
from 0 to m - 1
to pull out numbers, as your book suggests. j
, then, represents the number of integers that you have already pulled out of the bag.)
如果您是从现实生活中的包中挑选m
个整数,那么每次选择一个新数字时,您只会从包中拿走而不是从手中拿走.因此,remaining_num_elements
在每一步都会缩小.
If you're picking m
integers from a bag in real life, then every time you pick a new number, you take from the bag only and not from your hand. Thus, the remaining_num_elements
shrinks at each step.
以这种方式思考时,应该很容易看到这种方法可以保证每个元素被选择的可能性相等.
When you think this way, it should be simple to see that this method guarantees that each element has equal probability of being chosen.
这篇关于从大小为n的数组中随机生成一组m个整数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!