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

你可以这样做：创建一个列表，0.1000。洗牌。(见费舍-耶茨洗牌为了一个很好的方法来做这件事。)从被洗牌的列表中按顺序返回数字。因此，这不需要每次搜索旧值，但对于初始洗牌仍然需要O(N)。但正如Nils在评论中所指出的，这是摊销的O(1)。

Answer 3

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