我想要一个算法/函数,给定一个数字 N,在恒定时间内生成从 0 到 N - 1 的随机数。在第 N 次调用之后,该函数可以随心所欲地执行操作。此外,重要的是算法在请求时生成数字而不是使用混洗,因为我可能(并且在一般情况下不需要)不需要完整的数字列表。最好的方法是什么?
(可选阅读)我想到了一组哈希数字,并一次提取一个数字,但这需要先将所有元素(我通常不需要)插入哈希集中.. .这行不通...啊
提前感谢您的帮助。
最佳答案
修改Fisher–Yates shuffle通过用只存储已移动元素的映射替换数组。在 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) 个字。根据对数因子,这是最优的。
关于performance - 独特的随机数算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18326240/