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

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

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

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

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

Код 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 бита, во всяком случае).

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

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

Answer 1

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

1. Да, вы можете использовать LFSR для генерации перестановок с длиной, кратной 2. Вы также можете использовать любой блочный шифр. С блочным шифром вы также можете найти элемент по индексу n или по индексу для элемента n.
2. Чтобы сгенерировать перестановку произвольной длины l, создайте ее с наименьшей степенью длины 2, превышающей l. Когда вы хотите найти n-й элемент перестановки, примените функцию перестановки, и, если она генерирует число вне желаемого диапазона, примените его снова; повторяйте, пока число не окажется в приемлемом диапазоне.

Количество итераций, необходимых для шага 2, будет в среднем не более 2; худший случай высок, но крайне маловероятен.

Answer 2

Прежде всего, обратите внимание, что это не случайная последовательность. Он генерирует только одну фиксированную повторяющуюся последовательность, и начальное число выбирает, где в последовательности вы начинаете. Конечно, это то же самое, что и все PRNG, но обычно цикл PRNG намного больше, чем 16-битный или 32-битный. Как вы описали, используя его, длина цикла равна количеству элементов, по которым вы выполняете итерацию, так что все, что вам нужно будет сделать, это взять один "перемешанный" порядок и изменить то, с чего вы начинаете. Значение "seed" больше похоже на начальный индекс, чем на seed.

Это не самый удовлетворительный ответ, но он, вероятно, практичен: вы можете добавить длину до следующей степени двух и пропустить все индексы выше фактического максимума. Таким образом, если у вас есть 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))