为O唯一的（不重复）的随机数（1）？ [英] Unique (non-repeating) random numbers in O(1)?

问题描述

我想产生一个介于0和1000独特的随机数，永远不会重复（即6显示不出来两次），但是，这并不求助于像一个O（N）搜索previous值来做到这一点。这可能吗？

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和设置一个变量，最大，到阵列的当前的最大索引（从1000）。选择一个随机数R，在0和最大值，交换数在与数的位置r处位置max和现在返回数量在位置最大。按1递减max和继续。当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.

更新： 虽然我想到了我自己的这个方法时，我回答了这个问题，一些研究之后，我意识到这是对的费雪耶茨称为Durstenfeld - 费雪耶茨或克努特 - 费雪耶茨。由于描述可能有点难以理解，我已经提供了以下（使用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):

阵列与初始化数组[n] = N 11的元素开始了，最多在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    

在每次迭代中，随机数R选择在0到最大，阵[r]和阵列[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次迭代中，阵列中的所有数字都被选中，最大值== 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|
+--+--+--+--+--+--+--+--+--+--+--+

此时，最大可复位到10，这个过程可以继续进行。

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

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