O(1)中唯一(非重复)随机数？

Question

O(1)中唯一(非重复)随机数？我希望在0到1000之间生成唯一的随机数，这些数字永远不会重复(也就是说，6不会出现两次)，但这不需要使用O(N)搜索以前的值来实现。这个是可能的吗？

Answer 1

初始化值为0-1000的1001整数数组，并将变量max设置为数组的当前最大索引(从1000开始)。选择一个随机数，r，介于0和最大值之间，将位置r处的数字与位置max处的数字互换，然后在最大位置返回数字。最大减少1，然后继续。当max为0时，将max设置为数组的大小，然后在不需要重新初始化数组的情况下重新启动。

最新情况：虽然我在回答这个问题时自己想出了这个方法，但经过一些研究后，我意识到这是一个修改后的费舍-耶茨被称为杜斯滕菲尔德-费舍-耶茨或Knuth-Fisher-Yates。由于描述可能有点难以理解，我提供了以下示例(使用11个元素而不是1001)：

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

+--+--+--+--+--+--+--+--+--+--+--+

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

+--+--+--+--+--+--+--+--+--+--+--+

                                ^

                               max    

在每次迭代时，在0和max之间选择一个随机数r，交换数组[r]和数组[max]，返回新的数组[max]，并减少max：

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，数组元素被洗牌：

+--+--+--+--+--+--+--+--+--+--+--+

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

+--+--+--+--+--+--+--+--+--+--+--+

此时，可以将最大值重置为10，并且进程可以继续。

Answer 2

你可以这样做：

1. 创建一个列表，0.1000。
2. 洗牌。(见

   费舍-耶茨洗牌

   为了一个很好的方法来做这件事。)
3. 从被洗牌的列表中按顺序返回数字。

因此，这不需要每次搜索旧值，但对于初始洗牌仍然需要O(N)。但正如Nils在评论中所指出的，这是摊销的O(1)。

Answer 3

用最大线性反馈移位寄存器.

它可以在几行C中实现，在运行时，它只完成几个测试/分支、一点点加法和位移位。这不是随机的，但它愚弄了大多数人。