Создать произвольную перестановку 1..N в постоянном пространстве

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

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

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

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

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

1. Найдите простое число p больше N , предпочтительно не намного больше.
2. Найти примитивный корень из единицы g по модулю p , т. Е. Число 1 < g < p такое, что g^k ≡ 1 (mod p) тогда и только тогда, когда k кратно p-1 .
3. Проходим через g^k (mod p) при k = 1, 2, ... , игнорируя значения, большие 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 (√p), а поколение перестановок Θ (p), поэтому не имеет большого значения, что факторизация является оптимальной.

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

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

Рассмотрим премьер 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 к арифметике в своей собственной работе). Помимо этого, он работает со всеми простыми числами независимо от того, насколько они велики и перестановит всевозможные уникальные множества из них без необходимости в памяти за пару целых чисел (каждая технически требует немного меньше бит, чем сама прайм).

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

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

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

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

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

Здесь полезной является фундаментальная слабость генераторов LCG ( x=(x*m+c)%b ).

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

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

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

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

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

Вот какой код 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