唯一的随机数的算法(Unique random number algorithm)

在恒定时间1 - 我想的是，给定数量N的算法/函数，生成从0随机数到N。 第N个电话后，该功能可以为所欲为。 此外，重要的是，当请求，而不是使用洗牌算法生成的数字，因为我可以（并且在平均情况下都）不需要号码的完整列表。 什么是采取最好的方法？

（可选阅读）我想有一个哈希组数字，并一次拉号码的开出一个，但是这需要的所有元素（这是我经常不需要）插入到第一盘...这将哈希不行......哎呀

感谢提前任何帮助。

Answer 1:

修改费雪耶茨洗牌通过与地图存储仅已移动的元素取代该阵列。 在Python：

import random
class Shuffle:
    def __init__(self, n):
        self.d = {}
        self.n = n
    def generate(self):
        i = random.randrange(self.n)
        self.n -= 1
        di = self.d[i] if i in self.d else i  # idiomatically, self.d.get(i, i)
        dn = self.d[self.n] if self.n in self.d else self.n
        self.d[i] = dn
        self.d[self.n] = di
        return di

占用空间和预期摊销运行时间为O（1）实际产生每个元素的话。 截至记录的因素，这是最佳的。

文章来源: Unique random number algorithm