在Python中生成非重复的随机数
好吧，这是比听起来更棘手的问题之一，所以我转向堆栈溢出，因为我想不出一个好的答案。 这是我想要的：我需要Python生成一个简单的从0到1,000,000,000的数字列表随机顺序，用于序列号（使用一个随机数，以便你不能告诉有多less已经分配或做的时间攻击很容易，即猜测下一个将会出现）。 这些数字与链接到它们的信息一起存储在数据库表（索引）中。 生成它们的程序不会永远运行，所以它不能依赖于内部状态。
没什么大不了的 只要生成一个数字列表，把它们推到一个数组中，并使用Python“random.shuffle（big_number_array）”，我们就完成了。 问题是我想避免必须存储一个数字列表（从而读取文件，从顶部popup一个，保存该文件并closures它）。 我宁愿在飞行中产生它们。 问题是我能想到的解决scheme有问题：
1）生成一个随机数，然后检查它是否已被使用。 如果已经使用，则生成一个新的号码，检查，根据需要重复，直到find一个未使用的号码。 这里的问题是，我可能会得到不幸，并在获得一个未使用的数字之前产生大量使用的数字。 可能的解决方法：使用一个非常大的数字池来减less这个可能性（但是最后我得到了愚蠢的长数字）。
2）生成一个随机数，然后检查它是否已被使用。 如果已经使用过，请从数字中加上或减去一个，然后再次检查，继续重复，直到我点击一个未使用的数字。 问题是这不再是一个随机数，因为我已经引入了偏见（最终我会得到数字的团队，你可以预测下一个数字，更好的成功机会）。
3）生成一个随机数，然后检查它是否已被使用。 如果已经使用了加或减另一个随机生成的随机数并再次检查，问题是我们回到简单生成随机数并检查解决scheme1。
4）把它吸起来，并生成随机列表并保存它，让一个守护进程把它们放入一个队列中，这样就有了可用的数字（并避免不断地打开和closures一个文件，而不是一个文件）。
5）生成更大的随机数并散列它们（即使用MD5）以获得更小的数值，我们应该很less发生冲突，但是最终我会得到比所需数字更大的数字。
6）在随机数（即unix时间戳）上添加或附加基于时间的信息，以减less碰撞的机会，再次获得比我需要的更大的数字。
任何人都有任何聪明的想法可以减less“碰撞”（即产生一个已经采取的随机数）的机会，但也可以让我保持“小”（即less于十亿你的欧洲人=））。
答案，为什么我接受它：
所以我会简单的跟1一起去，希望这不是问题，但是如果是这样的话，我会用确定性的方法来生成所有的数字并存储它们，以便保证得到一个新的随机数，我可以使用“小号”（即9位而不是MD5 /等）。
这是一个很好的问题，我一直在思考这个问题（有类似于Sjoerd的解决scheme），但是最后我想：
用你的观点1），不要担心。
假定真实的随机性，之前已经select了随机数的概率是先前select的数字除以池的大小（即最大数）的数量。
如果你说你只需要十亿个数字，即九个数字：把自己再多处理3个数字，所以你有12位数的序列号（这是三组四位数 – 很好，可读）。
即使你已经接近select了十亿个数字，你的新号码已经被采用的概率仍然只有0.1％。
做第1步，再绘制。 你仍然可以检查一个“无限”循环，比如说不要尝试超过1000次左右，然后回退到加1（或者别的东西）。
在这个后备之前，你会赢得彩票。
您可以使用Format-Preserving Encryptionencryption计数器。 你的计数器从0开始向上，encryption使用你select的一个键把它变成一个看似随机的任意的基数和宽度。
分组密码通常具有例如64或128位的固定块大小。 但是保留格式encryption可以让你像AES一样采用标准密码，并且使用一个小宽度的密码，无论你想要什么样的基数和宽度（例如，基数为10，宽度为9的问题参数）密码强大。
保证不会发生冲突（因为密码algorithm创build1：1映射）。 这也是可逆的（双向映射），所以你可以把结果的数字，并返回到你开始的计数器值。
AES-FFX是实现这一目标的一种标准方法。
我已经对AES-FFX的一些基本的Python代码进行了实验 – 请参阅这里的Python代码 （但请注意，它并不完全符合AES-FFX规范）。 它可以例如将一个计数器encryption成一个随机的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密码进行FPE。 它产生从0到2 ^ 32-1的数字。
有了一些模块化的算术和素数，你可以创build0和一个大的素数之间的所有数字，不按顺序。 如果你仔细select你的号码，下一个号码很难猜测。
modulo = 87178291199 # prime incrementor = 17180131327 # relative prime current = 433494437 # some start value for i in xrange(1, 100): print current current = (current + incrementor) % modulo
如果他们不必是随机的，但不明显是线性的（1,2,3,4，…），那么这里有一个简单的algorithm：
选两个素数。 其中之一将是您可以产生的最大数量，所以它应该是十亿左右。 另一个应该是相当大的。
max_value = 795028841 step = 360287471 previous_serial = 0 for i in xrange(0, max_value): previous_serial += step previous_serial %= max_value print "Serial: %09i" % previous_serial
只要存储以前的序列每次，所以你知道你离开的地方。 我不能用math的方法来certificate这一点（从那些特殊的阶级开始就已经太长了），但是用较小的素数certificate是正确的：
s = set() with open("test.txt", "w+") as f: previous_serial = 0 for i in xrange(0, 2711): previous_serial += 1811 previous_serial %= 2711 assert previous_serial not in s s.add(previous_serial)
你也可以用9位素数来凭经validation明它，它只需要多一点工作（或更多的内存）。
这确实意味着只要给出几个序列号，就可以计算出你的值是什么 – 但是只有9位数字，不pipe怎么说你都不可能猜到数字。
如果你不需要密码保护的东西，但只是“充分混淆”…
伽罗瓦领域
您可以尝试在伽罗瓦域中进行操作，例如GF（2） 32 ，将简单的递增计数器x映射到看似随机的序列号y ：
x = counter_value y = some_galois_function(x)
- 乘以一个常数
- 逆是乘以常数的倒数
- 提高权力 ： x n
- 互惠x -1
- 提高权力的特例
- 这是它自己的反面
- 一个原始元素的幂指数 ： x
- 请注意，这没有一个容易计算的逆（离散对数）
- 确保a是一个原始元素 ，也就是生成器
这些操作中的许多操作都有相反的情况，这意味着，如果使用序列号，则可以计算从中导出的原始计数器值。
至于find伽罗瓦领域的Python图书馆…好问题。 如果你不需要速度（你不会这样做），那么你可以做你自己的。 我没有试过这些：
- NZMATH
- 有限的字段Python包
- Sage虽然是math计算的整体环境，但不仅仅是一个Python库
GF（2）中的matrix乘法
在GF（2）中select一个合适的32×32可逆matrix，并将其乘以一个32位input计数器。 这在概念上与LFSR相关，如S.Lott的回答中所述 。
CRC
相关的可能性是使用CRC计算。 基于GF（2）中的不可约多项式的长余数的余数。 Python代码已经可以用于CRC（ crcmod ， pycrc ），尽pipe你可能想要为你的目的select一个不同于通常使用的不可约多项式。 我对这个理论有些模糊，但我认为32位CRC应该为每个可能的4字节input组合产生一个唯一的值。 检查这个。 通过将输出反馈到input中，并检查它是否产生长度为2 32 -1的完整循环（零仅映射到零），可以很容易地通过实验来检查这一点。 您可能需要摆脱CRCalgorithm中的任何初始/最终异或，以使此检查正常工作。
我认为你高估了方法1）的问题。 除非你有硬实时要求，否则随机select检查会相当快速。 需要多次迭代的概率呈指数衰减。 在输出100M数字（10％填充因子）的情况下，您将有十亿次的机会需要超过9次迭代。 即使有50％的数字，你平均需要2次迭代，并有十亿分之一的机会需要超过30次的检查。 甚至在99％的数字已经被采用的极端情况下仍然是合理的 – 你将平均进行100次迭代，并且有1亿次变化需要2062次迭代
标准线性同余随机数发生器的种子序列不能重复，直到从起始种子值产生的全部数字已经产生。 那么它必须精确地重复。
内部种子通常很大（48或64位）。 生成的数字较小（通常为32位），因为整个位组不是随机的。 如果你遵循种子值，他们将形成一个独特的非重复序列。
这个问题本质上是find一个能产生“足够”数字的好种子。 你可以select一个种子，并产生数字，直到你回到起始种子。 这是序列的长度。 它可能是数百万或数十亿的数字。
Knuth有一些select合适种子的指导方针，这些种子会产生很长的独特数字序列。
你可以运行1），而不会遇到太多错误的随机数的问题，如果你只是每次减less一个随机间隔。
要使用这种方法，您需要保存已经提供的号码（无论如何您都要这样做），并保存所采用的号码数量。
很明显，在收集了10个数字之后，你的随机数可能会减less10个。因此，你不能select1到1.000.000之间的数字，但是在1到999.990之间。 当然这个数字不是真正的数字，只是一个索引（除非收集到的10个数字是999.991，999.992，…）; 您现在必须从1中删除已收集的所有数字。
当然，你的algorithm应该比从1到1000.000算起来更聪明，但是我希望你能理解这个方法。
我不喜欢画任意数字，直到find一个适合的数字。 这只是感觉不对。
我的解决schemehttps://github.com/glushchenko/python-unique-id ，我想你应该扩展matrix为10亿变化和乐趣。
我会重新考虑这个问题本身……你似乎没有做任何与数字相关的事情……而且你已经有了一个索引列。 他们真的需要成为数字吗？
考虑一下哈希…你并不需要整个事情。 做什么混帐或其他url缩短服务做，并采取散列的前3/4/5个字符。 鉴于每个字符现在有36个可能的值而不是10个，您有2,176,782,336个组合，而不是999,999个组合（对于六个数字）。 结合这一点，快速检查组合是否存在（一个纯粹的索引查询）和种子，如时间戳+随机数，它应该做几乎任何情况。
你需要这个密码安全或只是很难猜到？ 碰撞有多糟糕？ 因为如果它需要密码强大并且没有碰撞，那很遗憾是不可能的。
我开始尝试写下面使用的方法的解释，但只是实现它更容易，更准确。 这种方法有一个奇怪的现象，就是你生成的数字越多，速度越快。 但是，它的工作原理，并不需要你提前生成所有的数字。
作为一个简单的优化，你可以很容易地让这个类使用一个概率algorithm（生成一个随机数，如果它不在所使用的数字集中，把它添加到集合中并返回），跟踪冲突率，一旦碰撞率变差，切换到这里使用的确定性方法。
import random class NonRepeatingRandom(object): def __init__(self, maxvalue): self.maxvalue = maxvalue self.used = set() def next(self): if len(self.used) >= self.maxvalue: raise StopIteration r = random.randrange(0, self.maxvalue - len(self.used)) result = 0 for i in range(1, r+1): result += 1 while result in self.used: result += 1 self.used.add(result) return result def __iter__(self): return self def __getitem__(self): raise NotImplemented def get_all(self): return [i for i in self] >>> n = NonRepeatingRandom(20) >>> n.get_all() [12, 14, 13, 2, 20, 4, 15, 16, 19, 1, 8, 6, 7, 9, 5, 11, 10, 3, 18, 17]
如果一个偶然观察者不能猜测下一个值就足够了，那么可以使用线性同余生成器或简单的线性反馈移位寄存器来生成值并在数据库中保存状态更多的价值。 如果你正确地使用这些值，直到宇宙结束才会重复这些值。 你会发现更多的想法在随机数发生器的列表 。
如果您认为可能有人会怀疑猜测下一个值，那么您可以使用数据库序列来计算您生成的值，并使用encryptionalgorithm或其他encryptionalgorithm对其进行encryption。 但是，如果能够获得您生成的连续数字序列，则需要注意encryptionalgorithm不易被破坏 – 例如，一个简单的RSA就不会因Franklin-Reiter相关消息攻击 。
有点晚回答，但我没有看到这个build议任何地方。
为什么不使用uuid模块来创build全局唯一的标识符
要在定义的阈值内生成一个完全随机数列表，如下所示：
plist=list() length_of_list=100 upbound=1000 lowbound=0 while len(pList)<(length_of_list): pList.append(rnd.randint(lowbound,upbound)) pList=list(set(pList))
在碰到这个问题之前，我遇到了同样的问题，开了一个题目不同的问题 。 我的解决scheme是在间隔[0,maximal)的索引（即不重复的数字）的随机样本生成器，称为itersample 。 以下是一些用法示例：
import random generator=itersample(maximal) another_number=generator.next() # pick the next non-repeating random number
要么
import random generator=itersample(maximal) for random_number in generator: # do something with random_number if some_condition: # exit loop when needed break
itersample生成非重复的随机整数，存储需求被限制在选取的数字，并且selectn数字所需的时间应该是（如某些testing证实的） O(n log(n)) ，最大值的regardelss。
这是itersample的代码：
import random def itersample(c): # c = upper bound of generated integers sampled=[] def fsb(a,b): # free spaces before middle of interval a,b fsb.idx=a+(b+1-a)/2 fsb.last=sampled[fsb.idx]-fsb.idx if len(sampled)>0 else 0 return fsb.last while len(sampled)<c: sample_index=random.randrange(c-len(sampled)) a,b=0,len(sampled)-1 if fsb(a,a)>sample_index: yielding=sample_index sampled.insert(0,yielding) yield yielding elif fsb(b,b)<sample_index+1: yielding=len(sampled)+sample_index sampled.insert(len(sampled),yielding) yield yielding else: # sample_index falls inside sampled list while a+1<b: if fsb(a,b)<sample_index+1: a=fsb.idx else: b=fsb.idx yielding=a+1+sample_index sampled.insert(a+1,yielding) yield yielding
你说的是你把数字存储在数据库中。
那么，把所有的数字存储在那里都不是一件容易的事情，并且要求数据库有一个随机的未使用的数字？ 大多数数据库都支持这种请求。
例子
MySQL的：
SELECT column FROM table ORDER BY RAND() LIMIT 1
PostgreSQL的：
SELECT column FROM table ORDER BY RANDOM() LIMIT 1
