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

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

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

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

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

Источник

5 ответов

Решение

Основываясь на ответе Джейсона, я сделал простую и понятную реализацию в 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();
    }
}
Источник

Вот реализация 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,
Источник

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

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

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

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

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

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

Источник

Посмотрите мою статью о безопасных перестановках с блочными шифрами для одного способа сделать это.

Источник

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

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)
Источник
Другие вопросы по тегам