在Python中生成不重复的随机数

Question

好吧，这个问题听起来比实际要复杂，所以我来求助于Stack Overflow，因为我想不出一个好的解决办法。我的需求是：我需要用Python生成一个从0到1,000,000,000的数字列表，顺序是随机的，用于序列号（使用随机数字是为了让人无法知道已经分配了多少，或者不容易进行时间攻击，也就是猜测下一个会出现的数字）。这些数字会存储在一个数据库表中（有索引），并且会附带相关信息。生成这些数字的程序不会一直运行，所以不能依赖内部状态。

这听起来没什么大不了的，对吧？只需要生成一个数字列表，把它们放进一个数组，然后用Python的“random.shuffle(big_number_array)”就可以了，事情就解决了。问题是我想避免存储一个数字列表（因此需要读取文件，从顶部取出一个，保存文件并关闭它）。我更希望能实时生成这些数字。问题是我想到的解决方案都有一些问题：

1) 生成一个随机数字，然后检查它是否已经被使用。如果已经被使用，就生成一个新数字，检查，重复这个过程直到找到一个未使用的数字。问题在于我可能会运气不好，生成很多已经使用的数字，才找到一个未使用的。可能的解决办法是使用一个非常大的数字池来减少这种情况的发生（但这样我得到的数字就会变得很长）。

2) 生成一个随机数字，然后检查它是否已经被使用。如果已经被使用，就在这个数字上加一或减一，然后再检查，继续重复这个过程直到找到一个未使用的数字。问题是这样就不再是随机数字了，因为我引入了偏差（最终我会得到一堆数字，你就能更好地预测下一个数字）。

3) 生成一个随机数字，然后检查它是否已经被使用。如果已经被使用，就再生成一个随机数字加到原来的数字上或减去，检查再说，问题是我们又回到了像方案1那样简单地生成随机数字并检查。

4) 直接生成随机列表并保存，让一个后台程序把它们放进一个队列，这样就有数字可用（避免不断打开和关闭文件，而是批量处理）。

5) 生成更大的随机数字并进行哈希处理（比如使用MD5）来得到一个更小的数字值，碰撞的几率应该很小，但我又会得到比需要的更大的数字。

6) 在随机数字前面或后面加上基于时间的信息（比如Unix时间戳）来减少碰撞的几率，但我又会得到比需要的更大的数字。

有没有人有聪明的主意，可以减少“碰撞”的几率（也就是生成一个已经被占用的随机数字），同时又能让我保持数字“较小”（也就是少于十亿（或者一千百万，对于欧洲人来说 =））。

我接受的答案和原因：

所以我会选择方案1，希望这不会成为问题，但如果真的有问题，我会选择确定性的解决方案，生成所有数字并存储它们，以确保能得到一个新的随机数字，并且我可以使用“较小”的数字（也就是9位数字，而不是MD5等）。

Answer 1

通过一些模块运算和质数，你可以生成从0到一个大质数之间的所有数字，而且顺序是乱的。如果你仔细选择这些数字，下一个数字就很难被猜到。

modulo = 87178291199 # prime
incrementor = 17180131327 # relative prime

current = 433494437 # some start value
for i in xrange(1, 100):
    print current
    current = (current + incrementor) % modulo

Answer 2

你可以使用一种叫做格式保留加密的方法来加密一个计数器。这个计数器的值从0开始往上增加，而加密的过程会用你选择的一个密钥，把它变成一个看起来随机的值，格式和长度都可以自己决定。

通常，块加密算法的块大小是固定的，比如64位或128位。但格式保留加密允许你使用像AES这样的标准加密算法，制作一个更小的加密块，格式和长度都可以自己选择（比如问题中提到的10进制，9位数），而且这种算法在安全性上依然很强。

这种加密方式保证不会出现重复的结果（因为加密算法是1:1的映射）。而且它是可逆的（也就是2-way映射），所以你可以从加密后的数字再得到最开始的计数器值。

AES-FFX是实现这种加密的一种提议标准方法。

我试过用一些简单的Python代码来实现AES-FFX——这里有Python代码（不过要注意，它并没有完全符合AES-FFX的规范）。这个代码可以把计数器加密成一个看起来随机的7位十进制数字。例如：

0000000   0731134
0000001   6161064
0000002   8899846
0000003   9575678
0000004   3030773
0000005   2748859
0000006   5127539
0000007   1372978
0000008   3830458
0000009   7628602
0000010   6643859
0000011   2563651
0000012   9522955
0000013   9286113
0000014   5543492
0000015   3230955
...       ...

另外一个Python的例子，使用了另一种非AES-FFX的方法（我想是这样），可以参考这篇博客文章《如何生成账户号码》，它使用了Feistel密码来实现格式保留加密。这个方法可以生成从0到2^32-1的数字。

Answer 3

这个问题挺有意思的，我想了很久（我的想法和Sjoerd的解决方案类似），但最后我觉得可以这样看：

先按照你第一点的建议去做，不用太担心。

假设你生成的随机数是真正随机的，那么一个随机数之前已经被选中的概率就是之前选中的数字数量除以你可以选择的总数，也就是最大数字。

如果你说你只需要十亿个数字，也就是九位数，那就给自己多留三位数，这样你就有了12位的序列号（分成三组四位数，读起来也很方便）。

即使你快要选出十亿个数字了，新选的数字已经被选中的概率也只有0.1%。

按照第一步再抽一次吧。你还可以设置一个“无限”循环的检查，比如不要尝试超过1000次，如果还是没选到，就加1（或者其他方法）再试。

在你需要用到这种备用方案之前，你可能已经中了彩票了。