Генерация перетасованного диапазона с использованием PRNG вместо перетасовки

Question

Существует ли какой-либо известный алгоритм, который может генерировать перетасованный диапазон [0..n) в линейном времени и постоянном пространстве (когда вывод производится итеративно) при произвольном начальном значении?

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

Мне известен вопрос 162606 , но он не дает ответа на этот конкретный вопрос - для сопоставления индексов перестановок с перестановками, приведенными в этом вопросе, потребуется огромное пространство начальных значений.

В идеале, он будет действовать как LCG с периодом и диапазоном n, но искусство выбора a и c для LCG является тонким. Простое выполнение ограничений для a и c в полном периоде LCG может удовлетворить мои требования, но мне интересно, есть ли какие-нибудь лучшие идеи там.

Answer 1

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

import random
import math

def lcg(start, stop):
    N = stop - start

    # M is the next largest power of 2
    M = int(math.pow(2, math.ceil(math.log(N+1, 2))))

    # c is any odd number between 0 and M
    c = random.randint(0, M/2 - 1) * 2 + 1

    # M=2^m, so make (a-1) divisible by all prime factors and 4
    a = random.randint(0, M/4 - 1) * 4 + 1

    first = random.randint(0, M - 1)
    x = first
    while True:
        x = (a * x + c) % M
        if x < N:
            yield start + x
        if x == first:
            break

if __name__ == "__main__":
    for x in lcg(100, 200):
        print x,

Answer 2

Основываясь на ответе Джейсона , я сделал простую и понятную реализацию в C #. Найти следующую наибольшую степень двух больше, чем N. Это делает тривиальным генерирование a и c, поскольку c должно быть относительно простым (то есть не может делиться на 2, то есть нечетным), и (a-1) делится на 2, а (a-1) должно делиться на 4. Статистически для генерации следующего числа требуется 1-2 сравнения (так как 2N> = M> = N).

class Program
{
    IEnumerable<int> GenerateSequence(int N)
    {
        Random r = new Random();
        int M = NextLargestPowerOfTwo(N);
        int c = r.Next(M / 2) * 2 + 1; // make c any odd number between 0 and M
        int a = r.Next(M / 4) * 4 + 1; // M = 2^m, so make (a-1) divisible by all prime factors, and 4

        int start = r.Next(M);
        int x = start;
        do
        {
            x = (a * x + c) % M;
            if (x < N)
                yield return x;
        } while (x != start);
    }

    int NextLargestPowerOfTwo(int n)
    {
        n |= (n >> 1);
        n |= (n >> 2);
        n |= (n >> 4);
        n |= (n >> 8);
        n |= (n >> 16);
        return (n + 1);
    }

    static void Main(string[] args)
    {
        Program p = new Program();
        foreach (int n in p.GenerateSequence(1000))
        {
            Console.WriteLine(n);
        }

        Console.ReadKey();
    }
}

Answer 3

Звучит так, будто вам нужен алгоритм, который гарантированно создаст цикл от 0 до n-1 без повторов. Есть почти наверняка целая куча из них в зависимости от ваших требований; теория групп была бы наиболее полезной областью математики, если вы хотите углубиться в теорию, стоящую за ней.

Если вы хотите быстро и не заботитесь о шаблонах предсказуемости / безопасности / статистики, вероятно, LCG - самый простой подход. Страница википедии, на которую вы ссылаетесь, содержит этот (довольно простой) набор требований:

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

1. c и m относительно простые,
2. a - 1 делится на все простые множители m
3. a - 1 кратно 4, если m кратно 4

В качестве альтернативы, вы можете выбрать период N> = n, где N - наименьшее значение, которое имеет удобные числовые свойства, и просто отбросить любые значения, полученные между n и N-1. Например, самое низкое N = 2 ^k - 1> = n позволит вам использовать регистры сдвига с линейной обратной связью (LFSR). Или найдите свой любимый криптографический алгоритм (RSA, AES, DES и т. Д.) И, учитывая конкретный ключ, определите пространство N чисел, которые оно переставляет, и для каждого шага применяйте шифрование один раз.

Если n мало, но вы хотите, чтобы безопасность была высокой, это, вероятно, самый хитрый случай, поскольку любая последовательность S, вероятно, будет иметь период N, намного больший, чем n, но также нетривиальна для получения неповторяющейся последовательности чисел более короткий период, чем N. (например, если вы можете взять вывод S mod n и гарантировать неповторяющуюся последовательность чисел, это даст информацию о S, которую может использовать злоумышленник)

Answer 4

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

x = (x << 1) | f(x)

, где f (x) может вернуть только 0 или 1.

Если вы выберете хорошую функцию f, x будет циклически перебирать все значения от 1 до 2 ^ n-1 (где n - некоторое число), хорошим псевдослучайным образом. Примеры функций можно найти здесь , например для 63 значений вы можете использовать

f(x) = ((x >> 6) & 1) ^ ((x >> 5) & 1)

Answer 5

См. Мою статью о безопасных перестановках с блочными шифрами , чтобы узнать как это сделать.