迭代地生成自然数的排列

我有一个不寻常的问题,可能会或可能不会被问过(虽然我没有找到任何东西,但我可能只是寻找错误的流行语).

我的任务很简单:给出自然数字的"列表",直到N [0,1,2,... N - 1]我想要改变这个序列.例如,当我输入数字4时,一个可能的结果将是[3,0,1,2].随机性应该由一些种子确定(然而这对于大多数普通语言的PRNG来说是标准的).

天真的方法是实例化一个大小为N的数组,用数字填充它并使用任何改组算法.

然而问题是,这种方法的存储器复杂性是O(n),在我的特殊情况下是不易处理的.我的想法是,编写一个生成器,迭代地在结果列表中提供数字.

更确切地说,我想要一些以迭代方式提供数字的"算法".更确切地说,概念类看起来像这样:

class Generator {
   // some state
   int nextNumber(...) {
      // some magic
   }
}

并且迭代地调用nextNumber方法提供序列的编号(即[0,1,... N-1]的任何排列.当然,这个生成器实例的状态应该比O(n)具有更好的内存复杂性再一次(我什么也得不到).

有什么算法要做,我想要什么？

这是使用我在大约2年前写的平衡Feistel网络的格式保留加密的 Python 3中相当简单的实现.它可以在32位系统上执行N到2 ⁶⁴的索引排列,或在64位构建的Python上执行2 ¹²⁸.这是由于函数返回的整数的大小.请参阅查找系统的限制.使用可以返回更大位长的值的更高级的哈希函数并不难,但我不想让这段代码更复杂或更慢.hash()sys.hash_info

更新

我对之前的版本进行了一些小改进,并在评论中添加了一些更多信息.我们使用高位来代替使用散列函数返回的低位,这通常会改善随机性,特别是对于短位长度.我还添加了另一种散列函数,xxhash由扬科莱,其中工程作品多比Python的更好的hash为这个应用程序,特别是对于较短的位长,虽然它是一个慢一点.xxhash算法比内置算法具有更高的雪崩效应hash,因此产生的排列往往更加良好.

尽管此代码适用于较小的值,stop但它更适合处理stop >= 2**16.如果您需要置换较小的范围内它可能是一个好主意,只是使用random.shuffle上list(range(stop)).它会更快,并且它不会使用那么多RAM:list(range(2**16))在32位机器上消耗大约1280千字节.

您会注意到我使用字符串为随机数生成器播种.对于这个应用程序,我们希望随机数发生器具有足够的熵,并且使用大字符串(或bytes)是一种简单的方法,正如random模块文档提到的那样.即便如此,这个程序只能在stop很大的时候产生所有可能排列的一小部分.因为stop == 35有35个!(35阶乘)不同的排列,35!> 2 ¹³²,但我们的密钥的总位长仅为128,因此它们无法涵盖所有​​这些排列.我们可以增加Feistel轮数以获得更多的覆盖范围,但显然这对于​​大的值来说是不切实际的stop.

''' Format preserving encryption using a Feistel network

    This code is *not* suitable for cryptographic use.

    See https://en.wikipedia.org/wiki/Format-preserving_encryption
    https://en.wikipedia.org/wiki/Feistel_cipher
    http://security.stackexchange.com/questions/211/how-to-securely-hash-passwords

    A Feistel network performs an invertible transformation on its input,
    so each input number produces a unique output number. The netword operates
    on numbers of a fixed bit width, which must be even, i.e., the numbers
    a particular network operates on are in the range(4**k), and it outputs a
    permutation of that range.

    To permute a range of general size we use cycle walking. We set the
    network size to the next higher power of 4, and when we produce a number
    higher than the desired range we simply feed it back into the network,
    looping until we get a number that is in range.

    The worst case is when stop is of the form 4**k + 1, where we need 4
    steps on average to reach a valid n. In the typical case, where stop is
    roughly halfway between 2 powers of 4, we need 2 steps on average.

    Written by PM 2Ring 2016.08.22
'''

from random import Random

# xxhash by Yann Collet. Specialised for a 32 bit number
# See http://fastcompression.blogspot.com/2012/04/selecting-checksum-algorithm.html

def xxhash_num(n, seed):
    n = (374761397 + seed + n * 3266489917) & 0xffffffff
    n = ((n <<17 | n >> 15) * 668265263) & 0xffffffff
    n ^= n >> 15
    n = (n * 2246822519) & 0xffffffff
    n ^= n >> 13
    n = (n * 3266489917) & 0xffffffff
    return n ^ (n >> 16)

class FormatPreserving:
    """ Invertible permutation of integers in range(stop), 0 > self.shiftbits, n & self.lowmask
        for key in keys:
            left, right = right, left ^ (xxhash_num(right, key) >> self.lowshift)
            #left, right = right, left ^ (hash((right, key)) >> self.lowshift) 
        return (right <

产量

Shuffling a small number
0 4 0
1 2 1
2 5 2
3 9 3
4 1 4
5 3 5
6 7 6
7 0 7
8 6 8
9 8 9

Shuffling a small number, with a slightly different keystring
0 9 0
1 8 1
2 3 2
3 5 3
4 2 4
5 6 5
6 1 6
7 4 7
8 7 8
9 0 9

Here are a few values for a large maxn
maxn = 10000000000000000000
0: 7071024217413923554 0
1: 5613634032642823321 1
2: 8934202816202119857 2
3:  296042520195445535 3
4: 5965959309128333970 4
5: 8417353297972226870 5
6: 7501923606289578535 6
7: 1722818114853762596 7
8:  890028846269590060 8
9: 8787953496283620029 9

Using a set to test that there are no collisions...
maxn 100000
True

Testing that the operation is bijective...
yes
0 4
1 2
2 5
3 9
4 1
5 3
6 7
7 0
8 6
9 8


以下是如何使用它来制作发电机:

def ipermute(stop, keystring):
    fpe = FormatPreserving(stop, keystring)
    for i in range(stop):
        yield fpe.fpe(i)

for i, v in enumerate(ipermute(10, 'secret key string')):
    print(i, v)


产量

0 4
1 2
2 5
3 9
4 1
5 3
6 7
7 0
8 6
9 8




它的速度相当快(对于Python),但它绝对不适合加密.它可以通过增加扩展Feistel的数量舍入到至少5,并通过使用合适的密码散列函数,例如进行加密级Blake2.此外,需要使用加密方法来生成Feistel密钥.当然,除非你确切知道自己在做什么,否则不应该编写加密软件,因为编写易受时序攻击等影响的代码太容易了.

        

2> Matt Timmerm..：
你正在寻找的是一个函数形式的伪随机置换,比如f,它以伪随机双射方式将1到N的数字映射到1到N的数字.然后,要以伪随机排列生成第n个数,只需返回f(n)

这基本上与加密问题相同.具有密钥的分组密码是伪随机双射函数.如果按顺序将所有可能的纯文本块精确地输入一次,它将以不同的伪随机顺序返回所有可能的密文块.

因此,为了解决像你这样的问题,你基本上做的是创建一个密码,它可以处理从1到N而不是256位块或其他数字的数字.您可以使用加密工具来执行此操作.

例如,您可以使用Feistel结构(https://en.wikipedia.org/wiki/Feistel_cipher)构建您的置换函数,如下所示:


设W为floor(sqrt(N)),并将函数的输入设为x
如果x 
x =(x +(NW ^ 2))%N
重复步骤(2)和(3)若干次.你做得越多,结果越随机.步骤(3)确保x 


由于该函数由许多步骤组成,每个步骤将以0和N-1的数字以双射方式将数字从0映射到N-1,整个函数也将具有此属性.如果你输入从0到N-1的数字,你将以伪随机顺序将它们退回.