唯一的随机数的算法

本文介绍了唯一的随机数的算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I would like an algorithm/function that, given a number N, generates random numbers from 0 to N - 1 in constant time. After the Nth call, the function may do as it pleases. Also, it is important that the algorithm generates the numbers when requested rather than using shuffling, because I may (and in the average case do) not need the full list of numbers. What is the best approach to take?

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

(optional to read) I thought of having a hash set of numbers, and pulling the numbers out one at a time, but this would require inserting all elements (which I often do not need) into the hash set first... this will not work... Argh

感谢提前任何帮助。

推荐答案

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

Modify the Fisher–Yates shuffle by replacing the array with a map that stores only the elements that have been moved. In 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）实际产生的每个元素的话。达记录的因素，这是最佳的。

The space usage and amortized expected running time is O(1) words per element actually generated. Up to log factors, this is optimal.