Вопрос по algorithm, random – Создать случайную перестановку 1..N в постоянном пространстве

20

Я ищу перечислить случайную перестановку чисел 1..N в фиксированном пространстве. Это означает, что я не могу сохранить все номера в списке. Причина в том, что N может быть очень большим, больше доступной памяти. Я все еще хочу быть в состоянии пройти через такую перестановку чисел по одному, посещая каждое число ровно один раз.

Я знаю, что это можно сделать для определенных N: многие генераторы случайных чисел циклически перебирают все пространство состояний случайным образом, но полностью Хороший генератор случайных чисел с размером состояния 32 бита будет излучать перестановку чисел 0 .. (2 ^ 32) -1. Каждый номер ровно один раз.

Я хочу выбрать N, чтобы быть любым числом вообще и не быть ограниченным степенями 2, например. Есть ли алгоритм для этого?

Немного (очень) устарело, но у меня есть для вас решение, которое не предполагает "отбрасывать вещи" только потому, что мы не получили того, чего хотим ".iif N прост. Я очень не решаюсь опубликовать его (поскольку я все еще работаю над CSRNG на основе этой концепции), но я сделаю это в качестве ответа, но если вы все еще заинтересованы (и условия, описанные выше, соответствуют), я был бы готов , mr.stobbe
Я только что обнаружил эту статью:en.wikipedia.org/wiki/Pseudorandom_permutation Таким образом, этот процесс использования функции, которая сопоставляет ключи с перестановками, называется & # x2018;pseudorandom permutation& # x2019; и вопрос в том, как выбрать / реализовать / использовать алгоритм, реализующий такую функцию. В статье также упоминается связь между идеальными блочными шифрами и идеальной псевдослучайной перестановкой. James Haigh
Насколько случайным это должно быть? Например, может ли перечисление начинаться с одного и того же состояния и генерировать ту же последовательность, что и «нормальная»; генератор случайных чисел, или он должен каждый раз отличаться? gbulmer
@ mr.stobbe, это было бы отличным решением, так как у нас было бы так много простых чисел, которые мы отбросили бы очень мало для любого N. usr
@usr Позвольте мне уточнить ... этоonly работает еслиN прост. Нет, если вы ищете грубую силу между двумя простыми числами. Другими словами, это не решение, которое поможет вам найти перестановкиany задавать,only уникальные множества, которые просты в подсчете. (Следовательно,if-and-only-if.) mr.stobbe

Ваш Ответ

6   ответов
11

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

Другая возможность, которая в значительной степени является той же самой вариацией, состоит в том, чтобы использовать регистр сдвига с линейной обратной связью (LFSR) для генерации чисел в первую очередь. Это имеет несколько преимуществ: во-первых, LFSR, вероятно, немного быстрее, чем большинство PRNG. Во-вторых, (я считаю) немного проще спроектировать LFSR, который производит числа, близкие к желаемому диапазону, и при этом быть уверенным, что он циклически перебирает числа в своем диапазоне в (псевдо) случайном порядке, без каких-либо повторений.

Не тратя много времени на детали, математика LFSRs была изучена довольно тщательно. Создание того, которое проходит через все числа в его диапазоне без повторения, просто требует выбора набора «нажатий». которые соответствуют неприводимому многочлену. Если вы не хотите искать это самостоятельно, довольно легко найти таблицы известных таблиц практически для любого разумного размера (например, при быстром просмотре в статье в Википедии перечислены их размеры до 19 бит).

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

Важно понимать, что при использовании lfsr с жестко закодированными метками порядок является фиксированным, и начальное число только выбирает, где в этом фиксированном порядке начинать и заканчивать.
В соответствии сen.wikipedia.org/wiki/Maximum_length_sequence LFSR всегда отображают 0 на 0, и максимально возможная длина последовательности равна 2 & lt; sup & gt; n & lt; / sup & gt; - 1 где n - количество бит в регистре. Следовательно, количество возможных перестановок ограничено (2 & lt; sup & lt; / sup & gt; - 1)! в большинстве. Максимальная случайность достигается, когда случайный ключ вводится в функцию, которая единообразно отображает ключи в (2 & lt; sup & nt; / sup & gt;)! возможные перестановки.
9

Один из способов сделать это будет

  1. Find a prime p larger than N, preferably not much larger.
  2. Find a primitive root of unity g modulo p, that is, a number 1 < g < p such that g^k ≡ 1 (mod p) if and only if k is a multiple of p-1.
  3. Go through g^k (mod p) for k = 1, 2, ..., ignoring the values that are larger than N.

Для каждого простогоp, имеютсяφ(p-1) Примитивные корни единства, так что это работает. Однако это может занять некоторое время. В общем, найти подходящее простое число намного проще.

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

Поскольку число примитивных корнейφ(p-1), если один случайно выбираетr в диапазоне от 1 доp-1ожидаемое количество попыток, пока не будет найден примитивный корень,(p-1)/φ(p-1)следовательно, следует выбиратьp чтобыφ(p-1) относительно большой, это означает, чтоp-1 должно иметь несколько различных простых делителей (и, предпочтительно, только большие, кроме фактора 2).

Вместо случайного выбора можно также последовательно попробовать2, 3, 5, 6, 7, 10, ... это примитивный корень, который, конечно, пропускает совершенные способности (или нет, они вообще быстро уничтожаются), что не должно сильно влиять на количество попыток.

Так что сводится к проверке, является ли числоx это примитивный корень по модулюp, Еслиp-1 = q^a * r^b * s^c * ... с четкими простыми числамиq, r, s, ..., x является примитивным корнем тогда и только тогда, когда

x^((p-1)/q) % p != 1
x^((p-1)/r) % p != 1
x^((p-1)/s) % p != 1
...

таким образом, нужно приличное модульное возведение в степень (возведение в степень путем многократного возведения в квадрат поддается хорошо для этого, уменьшаясь на модуль на каждом шаге). И хороший способ найти главный фактор разложенияp-1, Отметим, однако, что даже наивное пробное разделение будет только O (& # x221A; p), в то время как генерация перестановки является & lt; (p), поэтому не первостепенно, что факторизация является оптимальной.

Для простого p существует ровно фи (p-1) различных примитивных корней, так что попытка выбрать случайный будет работать,mathworld.wolfram.com/PrimitiveRoot.html
Это звучит правильно. Любая идея, как я могу легко получить подходящий простой корень? Моя математика, безусловно, не до этой задачи. usr
Ах да, выбор случайной отправной точки - хорошая идея, @kilotaras.
Также для увеличения случайности вы можете выбрать начальную степень k0 случайным образом, то есть не через g ^ k (mod p), а через g ^ (k + k0).
Ах, это сложная часть. Я не знаю действительно хорошего способа, который гарантированно будет быстрым, но я могу предложить что-то, чтобы увеличить вероятность нахождения одного быстрого. Я буду редактировать, дай мне несколько минут (вероятно, больше, чем несколько).
0

Вот некоторыеSageMath код, который должен генерировать случайную перестановку в путиДаниэль Фишер предложил:

def random_safe_prime(lbound):
    while True:
        q = random_prime(lbound, lbound=lbound // 2)
        p = 2 * q + 1
        if is_prime(p):
            return p, q


def random_permutation(n):
    p, q = random_safe_prime(n + 2)

    while True:
        r = randint(2, p - 1)
        if pow(r, 2, p) != 1 and pow(r, q, p) != 1:
            i = 1
            while True:
                x = pow(r, i, p)
                if x == 1:
                    return

                if 0 <= x - 2 < n:
                    yield x - 2

                i += 1
4

Другой способ сделать это с помощью блочного шифра; увидетьэтот блог для деталей.

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

@usr Статья, на которую я ссылался, описывает, как это сделать. Вы можете взять существующий шифр и уменьшить его размер блока.
@JamesHaigh Если это поможет, я тоже написал статью.
Это будет работать Для генерации 27-битного случайного числа мне нужно найти какой-нибудь экзотический шифр с таким размером состояния, как я полагаю. Или выбросить 31/32 сгенерированных шифротекстов. usr
Хотя эта ссылка может ответить на вопрос, лучше включить сюда основные части ответа и предоставить ссылку для справки. Ответы, содержащие только ссылки, могут стать недействительными, если связанная страница изменится.
Я не одобряю это из-за отсутствия усилий, но из-за связанной статьи (и PDF, которыйthat ссылки на статьи) на самом деле очень полезно и, вероятно, должно быть принятым ответом. Для решения проблемы гиперссылки-гнили, упомянутой @ccjmne, вот архивная копия страницы:web.archive.org/web/20130517173425/http://blog.notdot.net/2007/…
2

Принципиальная слабость LCG (x=(x*m+c)%b Генераторы стилей) здесь полезно.

Если генератор сформирован правильно, тоx%f также повторяющаяся последовательность всех значений нижеf (предоставленаf если факторb).

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

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

К сожалению, LCG - плохой генератор по той же причине, что и приведенная выше.

Кроме того, это имеет тот же недостаток, как я отметил в комментарии к ответу @ JerryCoffin. Он всегда будет генерировать одну и ту же последовательность, и единственное, что контролирует семя, это то, с чего начать в этой последовательности.

2

Рассмотрим простое число 3. Чтобы полностью выразить все возможные результаты, подумайте об этом следующим образом ...

bias + step mod prime

bias это просто смещение смещения.step является аккумулятором (если он1 например, это было бы просто0, 1, 2 в то время как в то время как2 приведет к0, 2, 4) а такжеprime простое число, против которого мы хотим сгенерировать перестановки.

Например. Простая последовательность0, 1, 2 было бы...

0 + 0 mod 3 = 0
0 + 1 mod 3 = 1
0 + 2 mod 3 = 2

Изменив пару этих переменных на секунду, мы возьмемbias из1 а такжеstep из2 (только для иллюстрации) ...

1 + 2 mod 3 = 0
1 + 4 mod 3 = 2
1 + 6 mod 3 = 1

Вы заметите, что мы создали совершенно другую последовательность. Ни одно число в наборе не повторяется, и все числа представлены (это биективно). Каждая уникальная комбинация смещения и смещения приведет к одному изprime!  возможные перестановки множества. В случаеprime из3 вы увидите, что есть6 разные возможные перестановки:

0,1,2
0,2,1
1,0,2
1,2,0
2,0,1
2,1,0

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

1/3! = 1/6 = 1.66..

... против ...

1/3 (bias) * 1/2 (step) => 1/6 = 1.66..

Ограничения просты,bias должен быть в пределах0..P-1 а такжеstep должен быть в пределах1..P-1 (Я функционально только что использовал0..P-2 и добавление1 по арифметике в моей собственной работе). Кроме этого, он работает со всеми простыми числами, независимо от их размера, и будет переставлять все возможные уникальные их наборы без необходимости в памяти, кроме пары целых чисел (для каждого из них технически требуется чуть меньше битов, чем для простого числа).

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

Тем не менее, если вы хотите использовать этот метод для генерации последовательности набора, которая не является простым, у вас есть два варианта.

Во-первых (и самое простое / самое дешевое), выберите простое число, которое больше, чем размер, который вы ищете, и пусть ваш генератор просто отбрасывает все, что ему не принадлежит. Еще раз,dangerЭто очень плохая идея, если это приложение, чувствительное к безопасности.

Во-вторых (безусловно, самый сложный и дорогостоящий), вы можете распознать, что все числа состоят из простых чисел, и создать несколько генераторов, которые затем производят произведение для каждого элемента в наборе. Другими словами,n из6 будет включать в себя все возможные простые генераторы, которые могут соответствовать6 (в этом случае,2 а также3), умноженный в последовательности. Это и дорого (хотя математически более изящно), а также вводит временную атаку, так что это даже менее рекомендуется.

Наконец, если вам нужен генератор дляbias и илиstep... почему вы не используете другого из того же семейства :). Внезапно вы очень близки к созданию настоящих простых случайных выборок (что обычно непросто).

Мне нравится этот метод, так как он очень прост в реализации. Но в этом нет строгой безопасности, верно? Просто уточняю, вопрос не требует безопасности. usr
Вводимая информация = информация о перестановке, по-видимому, не обобщает перестановки из более чем 3 элементов; например, для n = 5, 1/5 (смещение) * 1/4 (шаг) = 1/20! = 1/5! = 1/120. Я не думаю, что вы можете указать перестановку для n & gt; 3 элементов, используя два числа, не превышающие n.
1/6 не равно 1,66 .. это опечатка?

Похожие вопросы