随机数生成器,每次只返回一个数字

Question

Python是否有一个随机数生成器,每次next()调用函数时都只返回一个随机整数？数字不应重复,并且生成器应在[1, 1 000 000]唯一的区间中返回随机整数.

我需要生成超过一百万个不同的数字,如果所有数字同时生成并存储在列表中,这听起来好像非常耗费内存.

Answer 1

您正在寻找具有完整周期的线性同余生成器.这将允许您在目标数字范围内获得伪随机序列的非重复数字.

实现LCG实际上非常简单,看起来像这样:

def lcg(a, c, m, seed = None):
    num = seed or 0
    while True:
        num = (a * num + c) % m
        yield num

然后,它只是归结为选择正确的值a,c以及m以保证LCG将产生一个完整周期(这是你获得非重复号码的唯一保证).正如维基百科的文章所解释的那样,以下三个条件必须成立:

1. m并且c需要相对素数.
2. a - 1 被所有主要因素整除 m
3. a - 1可以被4整除,如果m也可被4整除.

只需选择一个素数就可以很容易地保证第一个c.此外,这是最后可以选择的值,这最终将允许我们稍微混合序列.

然而,a - 1和之间的关系m更复杂.在整个期间LCG中,m是期间的长度.或者换句话说,它是您的数字来自的数字范围.所以这就是你通常首先选择的.在你的情况下,你想要m在身边1000000.因为这限制了你很多(在您所选择的选择正是你的最大数量可能难以a也是c),所以你也可以选择比大号码,直接跳过你的范围之外的所有号码后.

我们m = 1000000现在就选择吧.主要因素m是2和5.而且它也明显可被整除4.因此a - 1,我们需要一个2 * 2 * 5满足条件2和3 的倍数.让我们选择a - 1 = 160,所以a = 161.

因为c,我们使用的是一个在我们的范围之间的随机素数:c = 506903

把它放到我们的LCG中就可以得到我们想要的序列.我们可以从range(0 <= seed <= m)中选择任何种子值作为序列的起点.

所以让我们试一试,验证我们想到的实际效果.为此,我们只是从集合中收集生成器中的所有数字,直到我们重复一次.那时,我们应该m = 1000000在集合中有数字:

>>> g = lcg(161, 506903, 1000000)
>>> numbers = set()
>>> for n in g:
        if n in numbers:
            raise Exception('Number {} already encountered before!'.format(n))
        numbers.add(n)

Traceback (most recent call last):
  File "<pyshell#5>", line 3, in <module>
    raise Exception('Number {} already encountered before!'.format(n))
Exception: Number 506903 already encountered before!
>>> len(numbers)
1000000

这是正确的!因此,我们创建了一个伪随机数字序列,允许我们从我们的范围中获得非重复数字m.当然,按照设计,这个序列将始终是相同的,因此当您选择这些数字时,它只是随机的一次.只要保持上面提到的属性,您就可以切换值a并c获取不同的序列.

这种方法的最大好处当然是您不需要存储以前生成的所有数字.它是一个恒定空间算法,因为它只需要记住初始配置和先前生成的值.

当你进一步进入序列时,它也不会恶化.这是解决方案的一般问题,该解决方案只是继续生成随机数,直到找到之前未遇到过的新数据.这是因为生成的数字列表越长,使用均匀分布的随机算法命中不在该列表中的数字的可能性就越小.因此,获得第100万个数字可能会花费很长时间来生成基于内存的随机生成器.

但是,当然,使用这种简单的算法只执行一些乘法和一些加法并不是非常随机的.但是你必须记住,这实际上是大多数伪随机数发生器的基础.所以在random.random()内部使用这样的东西.这只是在m为很多大的,所以你不要有注意到它.