从大小为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 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.它如何在所有元素上保持相等?

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屋！