在Python中生成非重复随机数

这是一个很好的问题,我已经思考了一段时间(解决方案类似于 Sjoerd's ),但最后,我想:

运用你的观点,停止担忧。

假设真实随机性,之前已选择随机数的概率是先前选择的数除以池的大小,即最大数。

如果你说你只需要10亿个数字,即9个数字:请多给自己3个数字,这样你就有了12个数字的序列号(这是三组4个数字,既漂亮又可读)。

即使你之前已经选择了10亿个数字,你的新数字被采纳的概率仍然只有0.1%。

执行步骤1并再次绘制。您仍然可以检查“无限”循环,比如不要尝试超过1000次,然后回退到添加1(或其他内容)。

你可以用 Format-Preserving Encryption 加密计数器。计数器从0向上移动,加密使用您选择的密钥将其转换为任意基数和宽度的随机值。

分组密码通常具有固定的块大小,例如64或128位。但是,保留格式的加密允许您使用标准密码(如AES)和较小宽度的密码,无论您想要什么基数和宽度(例如,对于问题的参数,基数为10,宽度为9),使用一种仍然具有加密鲁棒性的算法。

保证不会发生冲突(因为加密算法创建1:1映射)。它也是可逆的(双向映射),因此您可以获取结果数字并返回开始时使用的计数器值。

AES-FFX 是实现这一目标的一种拟议标准方法。

see Python code here (但请注意,它并不完全符合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(我认为)方法,请参见 this blog post "How to Generate an Account Number"

使用一些模块化算术和素数,您可以创建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

如果它们不一定是随机的,但不是明显的线性(1,2,3,4,…),那么这里有一个简单的算法:

选择两个素数。其中一个将是你能产生的最大数量,因此应该在10亿左右。另一个应该相当大。

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

每次只需存储上一个序列号,就可以知道从哪里中断了。我无法从数学上证明这是可行的(从那些特定的类开始已经太久了),但对于较小的素数,这显然是正确的:

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位数字,你不太可能选择不可用的数字。

如果你不需要加密安全的东西,只需要“足够模糊”。。。

你可以试着做手术 Galois Fields ,例如GF(2) ³² x 一个看似随机的序列号 Y :

x = counter_value
y = some_galois_function(x)

• 乘以常数
• Raise to a power :
• 互惠的 x ^-1
  • 上台的特例
  • 这是它自己的反面
• Exponentiation 基本元素的定义: A.
  • 请注意,这没有一个容易计算的逆(离散对数)
  • A. 是一个 primitive element 又称作 generator

其中许多操作都有一个逆运算,这意味着,给定序列号,可以计算从中导出的原始计数器值。

至于为Python的Galois字段查找库。。。好问题。如果你不需要速度(这是你不需要的),那么你可以自己做。我没有试过这些:

• NZMATH
• Finite field Python package
• Sage ,虽然它是一个完整的数学计算环境,但远远不止是一个Python库

在GF(2)中选择一个合适的3232可逆矩阵,并用它乘以一个32位输入计数器。这在概念上与LFSR相关,如中所述 S.Lott's answer

华润

一个相关的可能性是使用 CRC 计算。基于GF(2)中一个不可约多项式的长除法余数。Python代码可随时用于CRC( crcmod , pycrc ),尽管出于您的目的,您可能希望选择不同于通常使用的不可约多项式。我在理论上有点模糊,但我认为32位CRC应该为每个可能的4字节输入组合生成唯一的值。看看这个。通过将输出反馈到输入,并检查它是否产生长度为2的完整循环,很容易通过实验来检查这一点 ³²

内部种子通常较大(48或64位)。生成的数字较小(通常为32位),因为整个位集合不是随机的。如果遵循种子值,它们将形成一个不同的非重复序列。

问题本质上是找到一个能产生“足够”数量的好种子。您可以拾取一个种子,并生成数字,直到返回到起始种子。这就是序列的长度。它可能是数百万或数十亿的数字。

Knuth中有一些准则,用于挑选能够产生非常长的唯一编号序列的合适种子。

如果每次只减少一个随机间隔,就可以运行1),而不会遇到过多错误随机数的问题。

很明显,在收集了10个数字后,您的可能随机数池将减少10个。因此,您不能选择介于1和1.000.000之间的数字,而是介于1和999.990之间的数字。当然,这个数字不是实数,只是一个索引(除非收集到的10个数字是999.991、999.992,);你现在必须从1开始计算,忽略所有已经收集的数字。

我不喜欢画随机数,直到我得到一个适合的。只是感觉不对。

https://github.com/glushchenko/python-unique-id ,我认为你应该将矩阵扩展为100000000个变体,并从中获得乐趣。

需要 数字 ?

考虑一下沙沙…实际上你并不需要全部的东西。执行git或其他url缩短服务所做的操作,并获取散列的前3/4/5个字符。假设每个字符现在有36个可能的值,而不是10个,那么您有2176782336个组合,而不是999999个组合(对于六位数字)。结合快速检查组合是否存在(纯索引查询)和种子(如时间戳+随机数),几乎在任何情况下都应该这样做。

你需要加密安全还是仅仅是难以猜测?碰撞有多严重?因为如果它需要加密能力强并且没有冲突,不幸的是,这是不可能的。

我开始尝试在下面对所使用的方法进行解释,但只是实现它更容易、更准确。这种方法有一个奇怪的行为,即生成的数字越多,速度就越快。但它是有效的,并且不需要您提前生成所有的数字。

作为一个简单的优化,您可以很容易地让这个类使用一个概率算法(生成一个随机数,如果它不在使用过的数集中,则将其添加到集合中并返回),首先跟踪冲突率,一旦冲突率变差,就切换到此处使用的确定性方法。

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]

如果一个偶然的观察者猜不出下一个值就足够了,你可以使用 linear congruential generator 甚至是一个简单的 linear feedback shift register 生成值并在数据库中保留状态,以防需要更多值。如果你正确地使用这些值,这些值在宇宙结束之前不会重复。你会发现更多的想法 list of random number generators

如果您认为可能有人对猜测下一个值非常感兴趣,则可以使用数据库序列对生成的值进行计数,并使用加密算法或其他加密功能对其进行加密。然而,你需要注意的是,如果你能掌握你生成的一系列连续数字,那么加密算法就不容易被破解——一个简单的例子 RSA ,例如,由于 Franklin-Reiter Related Message Attack .

为什么不使用 uuid 要创建的模块 globally unique identifiers

生成定义阈值内的完全随机数列表,如下所示:

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))

我遇到了同样的问题,打开了一个 question with a different title My solution 是间隔中索引(即非重复数字)的随机样本生成器 [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

生成非重复的随机整数,存储需求仅限于拾取的数字和拾取所需的时间 n 数字应该是(正如一些测试所证实的) O(n log(n)) maximal .

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

您正在声明将数字存储在数据库中。

大多数数据库都支持这样的请求。

例子

SELECT column FROM table
ORDER BY RAND()
LIMIT 1

PostgreSQL:

SELECT column FROM table
ORDER BY RANDOM()
LIMIT 1