O(1) 中的唯一(非重复)随机数? [英] Unique (non-repeating) random numbers in O(1)?

问题描述

我想生成 0 到 1000 之间从不重复的唯一随机数(即 6 不会出现两次)，但这不会求助于像 O(N) 搜索以前的值之类的事情要做它.这可能吗?

I'd like to generate unique random numbers between 0 and 1000 that never repeat (i.e. 6 doesn't show up twice), but that doesn't resort to something like an O(N) search of previous values to do it. Is this possible?

推荐答案

初始化一个包含 1001 个整数的数组，值为 0-1000，并将变量 max 设置为数组的当前最大索引(从 1000 开始).选择一个介于 0 和 max 之间的随机数 r，将位置 r 处的数字与位置 max 处的数字交换，然后返回当前位置 max 处的数字.将 max 减 1 并继续.当 max 为 0 时，将 max 设置回数组的大小 - 1 并重新开始，无需重新初始化数组.

Initialize an array of 1001 integers with the values 0-1000 and set a variable, max, to the current max index of the array (starting with 1000). Pick a random number, r, between 0 and max, swap the number at the position r with the number at position max and return the number now at position max. Decrement max by 1 and continue. When max is 0, set max back to the size of the array - 1 and start again without the need to reinitialize the array.

更新:虽然我在回答问题时自己想出了这个方法，但经过一番研究后，我意识到这是 Fisher-Yates 被称为 Durstenfeld-Fisher-Yates 或 Knuth-Fisher-Yates.由于描述可能有点难以理解，我在下面提供了一个示例(使用 11 个元素而不是 1001 个):

Update: Although I came up with this method on my own when I answered the question, after some research I realize this is a modified version of Fisher-Yates known as Durstenfeld-Fisher-Yates or Knuth-Fisher-Yates. Since the description may be a little difficult to follow, I have provided an example below (using 11 elements instead of 1001):

数组从 11 个元素开始，初始化为数组 [n] = n，最大从 10 开始:

Array starts off with 11 elements initialized to array[n] = n, max starts off at 10:

+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
                                ^
                               max    

在每次迭代中，在0和max之间选择一个随机数r，array[r]和array[max]交换，返回新的array[max]，max递减:

At each iteration, a random number r is selected between 0 and max, array[r] and array[max] are swapped, the new array[max] is returned, and max is decremented:

max = 10, r = 3
           +--------------------+
           v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                       +-----+
                       v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
     +--------------------+
     v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
                 +-----+
                 v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

...

经过11次迭代，数组中的所有数字都被选中，max == 0，数组元素被打乱:

After 11 iterations, all numbers in the array have been selected, max == 0, and the array elements are shuffled:

+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

此时可以将 max 重置为 10，该过程可以继续.

At this point, max can be reset to 10 and the process can continue.

这篇关于O(1) 中的唯一(非重复)随机数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！