独特的随机数算法

我想要一个算法/函数，给定数字N，在常量时间内生成从0到N-1的随机数。在第N次通话后，该功能可以随心所欲。此外，算法在请求时生成数字而非使用混洗非常重要，因为我可能（并且在平均情况下）不需要数字的完整列表。最好的方法是什么？独特的随机数算法

（可选择阅读）我认为有一个数字散列集合，并且一次只提取一个数字，但这需要先将所有元素（我经常不需要）插入散列集合。 ..这将无法正常工作... Argh

感谢您的任何帮助提前。

来源

2013-08-20 tomKPZ

你正在要求一个没有明确随机播放的随机播放功能吗？你确实意识到在N-1次调用之后，返回值不再是非常随机的，对吗？我想一个按顺序返回数字的函数（和其他任何“洗牌”一样可能）不能满足你的需求。也许你想在你的要求中更具体一些？为什么不在第一个电话上洗牌？ – Floris

我不想在第一次调用时洗牌，因为元素列表很大，我平均只需要遍历前几个元素。 – tomKPZ

此外，通过“恒定时间”，你的意思是每次通话的时间完全相同，或者只是O（1）？此外，你完全不清楚你想要什么概率分布 - 一致随机是最简单的，但你的规格似乎暗示你想要别的东西。 –

修改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）个字。取决于对数因子，这是最佳的。

来源

2013-08-20 03:09:41

弗洛伊德的算法更简单，更快。 –

弗洛里斯上面的评论有一个链接。你在这里如何实现它的具体细节取决于你的需求，但仍不清楚。这个集合和子集有多大？你需要一个有序集合还是只是一个组合？ –

@LeeDanielCrocker Floyd算法需要提前知道调用次数，并且不需要额外的工作就不会产生均匀的随机排列。 –

独特的随机数算法

回答

相关问题