algorithm - 迭代生成自然数的排列

Question

我有一个有点不寻常的问题，之前可能会或可能不会被问过（虽然我没有找到任何东西，但是我可能只是在寻找错误的流行语）。

我的任务很简单：给定自然数的“列表”，直到 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) 更好的内存复杂度再次（我将一无所获）。

有什么算法可以做，我想要什么？

标签： algorithmpermutation

Answer 1

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

更新

我对之前的版本做了一些小的改进，并在评论中添加了更多信息。我们不使用从哈希函数返回的低位，而是使用高位，这通常会提高随机性，尤其是对于短位长度。我还添加了另一个哈希函数，Yann Collet 的 xxhash，它在这个应用程序中的工作效果比 Python 的要好得多，hash尤其是对于较短的位长度，虽然它有点慢。xxhash 算法比内置算法具有更高的雪崩效应hash，因此得到的排列往往更容易被洗牌。

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

你会注意到我使用一个字符串作为随机数生成器的种子。对于这个应用程序，我们希望随机化器有足够的熵，并且使用大字符串（或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 < stop <= 2**64
        using a simple Feistel network. NOT suitable for cryptographic purposes.
    """
    def __init__(self, stop, keystring):
        if not 0 < stop <= 1 << 64:
            raise ValueError('stop must be <=', 1 << 64)

        # The highest number in the range
        self.maxn = stop - 1

        # Get the number of bits in each part by rounding
        # the bit length up to the nearest even number
        self.shiftbits = -(-self.maxn.bit_length() // 2)
        self.lowmask = (1 << self.shiftbits) - 1
        self.lowshift = 32 - self.shiftbits

        # Make 4 32 bit round keys from the keystring.
        # Create an independent random stream so we
        # don't intefere with the default stream.
        stream = Random()
        stream.seed(keystring)
        self.keys = [stream.getrandbits(32) for _ in range(4)]
        self.ikeys = self.keys[::-1]

    def feistel(self, n, keys):
        # Split the bits of n into 2 parts & perform the Feistel
        # transformation on them.
        left, right = n >> 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 << self.shiftbits) | left

    def fpe(self, n, reverse=False):
        keys = self.ikeys if reverse else self.keys
        while True:
            # Cycle walk, if necessary, to ensure n is in range.
            n = self.feistel(n, keys)
            if n <= self.maxn:
                return n

def test():
    print('Shuffling a small number')
    maxn = 10
    fpe = FormatPreserving(maxn, 'secret key string')
    for i in range(maxn):
        a = fpe.fpe(i)
        b = fpe.fpe(a, reverse=True)
        print(i, a, b)

    print('\nShuffling a small number, with a slightly different keystring')
    fpe = FormatPreserving(maxn, 'secret key string.')
    for i in range(maxn):
        a = fpe.fpe(i)
        b = fpe.fpe(a, reverse=True)
        print(i, a, b)

    print('\nHere are a few values for a large maxn')
    maxn = 10000000000000000000
    print('maxn =', maxn)
    fpe = FormatPreserving(maxn, 'secret key string')
    for i in range(10):
        a = fpe.fpe(i)
        b = fpe.fpe(a, reverse=True)
        print('{}: {:19} {}'.format(i, a, b))

    print('\nUsing a set to test that there are no collisions...')
    maxn = 100000
    print('maxn', maxn)
    fpe = FormatPreserving(maxn, 'secret key string')
    a = {fpe.fpe(i) for i in range(maxn)}
    print(len(a) == maxn)

    print('\nTesting that the operation is bijective...')
    for i in range(maxn):
        a = fpe.fpe(i)
        b = fpe.fpe(a, reverse=True)
        assert b == i, (i, a, b)
    print('yes')

if __name__ == "__main__":
    test()

输出

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 密钥。当然，除非您确切地知道自己在做什么，否则不应该编写加密软件，因为编写容易受到定时攻击等的代码太容易了。