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

Ответ 1

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

Рассмотрим число 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 of 2 (только для иллюстрации)...

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

Вы заметите, что мы произвели совершенно другую последовательность. Число внутри набора не повторяется, и все числа представлены (они биективны). Каждая уникальная комбинация смещения и смещения приведет к одной из prime! возможных перестановок набора. В случае a prime of 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..

... vs...

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

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

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