如何在不提前生成整个序列的情况下生成可预测的序列洗牌？

Question

下面的Python代码正好描述了我想要实现的功能，适用于任意大小的序列（种群）：

import random
fixed_seed = 1 #generate the same sequence every time with a fixed seed
population = 1000
sample_count = 5 #demonstration number
num_retries = 3  #just enough to show the repeatable behaviour
for trynum in xrange(num_retries):
    #generate the fresh/ordered sequence (0->population)...
    seq = range(population)
    #seed the random number generator the same way every time...
    random.seed(fixed_seed)
    #shuffle the sequence...
    random.shuffle(seq)
    #display results for this try...
    sample_sequence = [str(x) for x in seq[:sample_count]]
    print "try %s: %s..." % (trynum + 1, ", ".join(sample_sequence))
#Sample output...
#try 1: 995, 721, 62, 326, 541...
#try 2: 995, 721, 62, 326, 541...
#try 3: 995, 721, 62, 326, 541...

这个方法的问题在于，它需要先把整个序列都生成到内存中。这对于非常大的种群来说可能会造成问题。

需要注意的是，这种方法的一个潜在大优点是，你可以随时从任何数组位置获取数据。

现在，如果当前的问题允许你将种群大小设置为2的幂（减去1），那么可以使用线性反馈移位寄存器（LFSR）来生成可预测的随机序列。LFSR很有意思，维基百科上的文章对它的解释也很不错。

下面的Python代码演示了这一点（我进行了大量的唯一性测试，以确保它如宣传的那样工作）。再次查看维基百科文章，了解代码是如何工作的（Galois配置）。

TAP_MASKS = { #only one needed, but I included 3 to make the code more useful
    10: 0x00000240, #taps at 10, 7
    16: 0x0000B400, #taps at 16, 14, 13, 11
    32: 0xE0000200, #taps at 32, 31, 30, 10
}

def MaxLengthLFSR(seed, register_length):
    "Gets next value from seed in max-length LFSR using Galois configuration."
    lsb = seed & 1
    next_val = seed >> 1
    if lsb == 1:
        mask = TAP_MASKS[register_length]
        next_val ^= mask
    return next_val

reglen = 16  #number of bits in register
population = (2**reglen) - 1 #not used, just showing it
fixed_seed = 1   #seed == startval in this case (could randomize in population)
sample_count = 5 #demonstration number
num_retries = 3  #just enough to show the repeatable behaviour
for trynum in xrange(num_retries):
    next_val = fixed_seed
    seq = [fixed_seed, ]
    for x in xrange(sample_count - 1):
        next_val = MaxLengthLFSR(next_val, reglen)
        seq.append(next_val)
    seq = [str(x) for x in seq]
    print "try %s: %s..." % (trynum + 1, ", ".join(seq))
#Sample output...
#try 1: 1, 46080, 23040, 11520, 5760...
#try 2: 1, 46080, 23040, 11520, 5760...
#try 3: 1, 46080, 23040, 11520, 5760...

这很好，因为你可以拥有一个巨大的种群，并且轻松计算出一个可重复且不重复的随机数序列，而不需要占用大量内存。

缺点是：a) 它限制在“洗牌”大小为(2**N - 1)的序列，b) 你无法在随机序列的任意位置确定特定位置的值。你需要知道某个特定点的值，然后从那里开始遍历序列。

后者（b）大多数情况下是可以接受的，因为你通常会按顺序生成序列，所以只需记住最后一个值即可。不过，2的幂限制（a）可能会让人觉得不太方便……这要看具体应用。

如何实现最大长度的LFSR样式的非重复结果，以适应任意长度的序列？

作为额外的好处，如果能有一个解决方案，让你能够在给定的序列位置直接知道数字，而不需要遍历到那个位置，那就更好了。

---

注意：如果你想要一个好的起始LFSR抽头位置集合，用于最大长度的LFSR（能够生成整个寄存器种群而不重复一次），这个链接非常不错，并且提供了每个寄存器大小的大量抽头位置（至少到32位）。

另外，请注意，我看到过很多与我的问题和洗牌/LFSR密切相关的问题，但没有一个完全符合我的需求（可预测的任意大小线性序列洗牌）。或者至少就我理解的来说是这样。

我最近在研究线性同余生成器，看起来很有前景，但我还没能让它们工作。与其继续等待这个问题，我决定提出来，如果我搞明白了并且它们能工作，我会把答案发出来。

Answer 1

首先要注意，这不是一个随机的序列。它只生成一个固定的、重复的序列，而“种子”决定了你从这个序列的哪个位置开始。这和所有的伪随机数生成器（PRNG）是一样的，不过通常情况下，PRNG的循环周期要比16位或32位大得多。你描述的使用方式中，循环的长度正好等于你要遍历的项目数量，所以它只会取一个“洗牌”后的顺序，并改变你开始的位置。这里的“种子”值更像是一个起始索引，而不是传统意义上的种子。

这可能不是最令人满意的答案，但在实际操作中是可行的：你可以把长度填充到下一个2的幂次方，然后跳过实际最大值以上的索引。因此，如果你有5000个项目，就生成一个8192个项目的序列，然后丢弃在[5000,8191]之间的结果。虽然这样做的开销听起来不太好，但从整体来看其实还好：因为这最多只会让列表的长度翻倍，平均来说你需要丢弃一半的结果，所以最坏情况下的平均开销就是工作量翻倍。

下面的代码演示了这一点（同时也展示了一种更简洁的实现方式）。MaxLengthLFSR的第三个参数，如果提供的话，就是实际的最大值。你可能想要为更多的大小填充TAP_MASKS，然后选择适合请求的序列长度的最小寄存器大小；这里我们只是使用了请求的那个，虽然这样可以工作，但如果序列的长度远大于需要的长度，会导致更多的开销。

TAP_MASKS = { # only one needed, but I included 3 to make the code more useful
    10: 0x00000240, # taps at 10, 7
    16: 0x0000B400, # taps at 16, 14, 13, 11
    32: 0xE0000200, # taps at 32, 31, 30, 10
}

def MaxLengthLFSR(next_val, reglen, max_value=None):
    """Iterate values from seed in max-length LFSR using Galois configuration."""
    # Ensure that max_value isn't 0, or we'll infinitely loop without yielding any values.
    if max_value is not None:
        assert max_value > 0

    while True:
        if max_value is None or next_val < max_value:
            yield next_val

        lsb = next_val & 1
        next_val = next_val >> 1
        if lsb == 1:
            mask = TAP_MASKS[reglen]
            next_val ^= mask

sample_count = 5 # demonstration number
num_retries = 3  # just enough to show the repeatable behaviour
for trynum in xrange(num_retries):
    it = MaxLengthLFSR(1, 16, 2000)
    seq = []
    for x in xrange(sample_count):
        seq.append(next(it))
    seq = [str(x) for x in seq]
    print "try %s: %s..." % (trynum + 1, ", ".join(seq))

Answer 2

我之前其实写过关于这个话题的内容：用块密码生成安全的排列。简单来说就是：

1. 没错，你可以用LFSR（线性反馈移位寄存器）来生成长度为2的幂的排列。你也可以使用任何块密码。用块密码的话，你还可以找到第n个元素，或者说某个元素的索引。
2. 如果你想生成任意长度l的排列，先生成一个比l大的最小的2的幂的长度。当你想找到第n个排列元素时，应用排列函数，如果生成的数字超出了你想要的范围，就再应用一次；一直重复，直到生成的数字在可接受的范围内。

第二步所需的迭代次数平均不会超过2次；虽然最坏的情况可能会很高，但发生的可能性极小。