如何在不預先生成整個序列的情況下生成序列的可預測混洗？

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很整齊，並且在他們的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, 46080, 23040, 11520, 5760... 
#try 3: 1, 46080, 23040, 11520, 5760... 

這是很好，因爲你可以有一個龐大的人口和方便地計算出可重複不重複的隨機數序列，而無需使用大內存塊。

缺點是a）僅限於大小爲（2 ** N-1）的「混洗」序列，以及b）您無法確定隨機序列中特定位置的值是什麼任意位置。你需要知道某個特定點的價值，然後從那裏走過去。

後者（b）大多數都是正常的，因爲大多數時候你會按順序生成序列，所以你只需要記住最後一個值。 2限制（a）的力量是一種交易殺手，儘管...取決於應用程序。

對於任意序列長度，您如何獲得最大長度LFSR類型的非重複結果？

作爲一個獎勵，最好有一個解決方案，您可以在給定的序列位置上知道數字，而無需遍歷序列到該位置。

---

注意：如果你想有一個很好的起點設置爲最大長度的LFSR LFSR的抽頭位置（即不重複一次生成整個報考人數的），this link is quite good的並且每個寄存器大小抽頭位置數量龐大（無論如何高達32位）。

另請注意，我已經看到了許多與我的問題和洗牌/ LFSR密切相關的問題，但他們中沒有一個與我之後的內容（任意大小的線性序列的可預測洗牌）完全相關。至少就我所能理解的而言，無論如何。

我最近一直在尋找Linear Congruential Generators，這看起來很有希望，但我還沒有能夠讓他們工作。我會問這個問題，而不是坐在這個問題上，如果我弄清楚它們的工作原理併發布答案。

Answer 1

我之前已經寫過關於這個的：Secure Permutations with Block Ciphers。簡而言之：

1. 是的，您可以使用LFSR生成長度爲2的排列。您還可以使用任何分組密碼。使用分組密碼，還可以在索引n處找到元素，或者在元素n處找到索引。
2. 要生成任意長度爲l的置換，請創建一個長度大於1的最小冪次方。當你想找到第n個置換元素時，應用排列函數，如果它產生了一個超出所需範圍的數字，再次應用它;重複，直到數字在可接受的範圍內。

步驟2所需的迭代次數平均不會超過2次;最壞的情況很高，但極不可能發生。

Answer 2

首先，請注意，這不是一個隨機序列。它只產生一個固定的重複序列，並且種子選擇你開始序列中的哪個位置。當然，這與所有的PRNG相同，但通常PRNG的週期遠遠大於16位或32位。您描述使用它的方式，週期長度爲等於，因爲您要迭代的項目數量很多，所以它只會執行一個「混洗」順序並更改您開始的位置。 「種子」值更像是一個起始索引而不是種子。

這不是最令人滿意的答案，但它可能是實用的：您可以將長度填充到下一個二次方，並跳過高於實際最大值的任何索引。因此，如果您有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))