Как сгенерировать предсказуемую перетасовку последовательности, не создавая ее заранее?

Следующий код 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...

Проблема с этим методом заключается в том, что он требует генерации всего последовательность в памяти первой. Это может быть проблемой для огромных групп населения.

Обратите внимание, что потенциально большим преимуществом этого метода является то, что вы можете выбрать любую позицию массива в любое время.

Теперь - если проблема под рукой. позволяет установить размер популяции в степени двойки (минус 1), регистр сдвига с линейной обратной связью можно использовать для получения предсказуемой случайной последовательности. LFSR аккуратны и довольно хорошо объяснены в статье википедии .

Код Python ниже демонстрирует это (и я провел кучу тестов на уникальность, чтобы убедиться, что он работает так, как рекламируется). См. статью в википедии еще раз для объяснения того, как работает код ( Конфигурация Галуа ).

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...

Это хорошо, потому что вы можете иметь ОГРОМНУЮ популяцию и легко вычислить повторяемую непроверенную повторение последовательности случайных чисел без использования большого фрагмента памяти.

Недостатками являются: а) то, что она ограничена "перетасовкой" последовательностей размера (2 ** N - 1), и б) то, что вы не можете определить, что значение конкретной позиции в случайной последовательности находится в произвольном месте. Вам нужно знать значение в определенной точке и пройти последовательность оттуда.

Последнее (b) в основном нормально, так как большую часть времени вы будете генерировать последовательность по порядку, поэтому вам просто нужно запомнить последний стоимость. Сила ограничения 2 (а) - своего рода убийца сделки, хотя ... в зависимости от приложения.

Как добиться неповторяющихся результатов, подобных LFSR максимальной длины, для произвольной длины последовательности?

В качестве бонуса было бы неплохо иметь решение, в котором вы можете узнать номер в данной позиции последовательности без необходимости переходить через последовательность к этой позиции.

Примечание: если вам нужен хороший начальный набор LFSR точки подключения для LFSR максимальной длины (которые генерируют всю совокупность регистров без единого повторения), эта ссылка неплохая и имеет огромное количество ответвлений на размер регистра (в любом случае до 32 бит).

Также обратите внимание, что я видел много вопросов, тесно связанных с моим вопросом и shuffling / LFSR, но ни один из них точно не относится к тому, что мне нужно (предсказуемое перемешивание линейной последовательности произвольного размера). По крайней мере, насколько мне удалось их понять.

Недавно я изучал Линейные конгруэнтные генераторы , которые кажутся многообещающими, но я не смог их найти пока работать. Вместо того, чтобы сидеть на вопросе, я задам его и отправлю ответ, если у меня получится, и они сработают.