概述

以下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,541...
#try 3: 995,541...

该方法的问题在于它需要生成整个
首先在内存中排序.对于庞大的人群来说,这可能是个问题.

请注意,此方法的一个潜在巨大优势是您可以随时选择任何阵列位置.

现在 – 如果手头的问题恰好让您将人口规模设置为2的幂
(减1),线性反馈移位寄存器可用于获得可预测的随机序列. LFSR很整洁,在wikipedia article上很好地解释了它们.

下面的python代码演示了这一点(我做了一堆唯一性测试,以确保它像宣传的那样工作).有关代码如何工作的说明,请再次参见wikipedia article(Galois configuration).

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,5760...
#try 3: 1,5760...

这很好,因为你可以拥有一个巨大的数量,并且可以轻松计算一个可重复的非重复随机数序列,而无需使用大块内存.

缺点是a)它被限制为大小(2 ** N-1)的“混洗”序列,并且b)你无法确定随机序列中特定位置的值是在任意位置.您需要知道特定点的值并从那里走序列.

后者(b)大部分都可以,因为大多数情况下你会按顺序生成序列,所以你只需要记住最后一个值. 2限制(a)的力量是一种交易杀手,但……取决于应用程序.

对于任意序列长度,如何实现最大长度-LFSR类非重复结果？

作为奖励,最好有一个解决方案,让您能够知道给定序列位置的数字,而无需遍历序列到该位置.

注意：如果你想要一个良好的起始LFSR抽头位置来获得最大长度的LFSR(产生整个寄存器的数量而不重复一次),this link is quite good并且每个寄存器大小具有大量抽头位置(最多32位,无论如何).

另请注意,我已经看到许多与我的问题和改组/ LFSR密切相关的问题,但它们都没有完全与我所追求的相关(任意大小的线性序列的可预测的随机播放).或者至少就我能够理解它们而言,无论如何.

我最近一直在研究Linear Congruential Generators,看起来很有希望,但我还没能让它们继续工作.我不会再问这个问题,而是如果我弄明白并且他们工作的话就发布答案.

>是的,您可以使用LFSR生成长度为2的幂的排列.您还可以使用任何分组密码.使用块密码,您还可以在索引n处找到元素,或者在元素n中找到索引.
>要生成任意长度为l的置换,请创建一个长度大于l的2的最小幂.如果要查找第n个排列元素,请应用置换函数,如果它生成超出所需范围的数字,则再次应用它;重复,直到数字在可接受的范围内.

步骤2所需的迭代次数平均不超过2次;最糟糕的情况是很高,但极不可能发生.

总结

以上是编程之家为你收集整理的如何在不事先生成整个序列的情况下生成序列的可预测混乱？全部内容，希望文章能够帮你解决如何在不事先生成整个序列的情况下生成序列的可预测混乱？所遇到的程序开发问题。

如果您也喜欢它,动动您的小指点个赞吧