Генерация случайной последовательности без повторов

Question

Я прочитал пару постов здесь о генерации случайной последовательности без повторов (например, Создать последовательность случайных чисел без повторов ) и решил реализовать ее для собственных нужд

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

Возможны по крайней мере несколько операций, таких как обмен двух битов, инвертирование бита, циклический сдвиг.Если мы используем только упомянутые, качество последовательности не будет высоким, так как соседний счетчик будет давать результаты с одинаковым количеством нулей и единиц.Реальный изменитель игры был xor один за другим.Теперь последовательности выглядят намного лучше, но вопросы таковы:

• Существует ли наименьшее подмножество операций, которых будет достаточно (например, инвертировать бит + бит xor на другой бит), и добавление любого другого простоусложнить чтение алгоритма, не предоставляя дополнительных преимуществ
• Как можно приблизительно угадать количество операций для заданного диапазона, чтобы последовательность была достаточно хорошей.Например, 200 операций для чисел от 0 до 31 дают визуально хорошие результаты, но 200 операций для диапазона 0..199 иногда дают блоки близких чисел.
• Существует ли алгоритм или набор тестов для тестирования таких последовательностей,Я знаю и однажды использовал наборы, которые могут тестировать общие случайные последовательности, но этот отличается, поэтому, возможно, нужен какой-то специальный набор или, по крайней мере, какое-то преобразование обратно в общий случайный мир

ОБНОВЛЕНИЕ:Как я уже писал в комментарии, уже есть такой генератор: шифрование AES, но, к сожалению, его можно использовать только для 128-битных диапазонов.

Спасибо

Макс

Answer 1

Проблема:

Создание списка уникальных случайных чисел от 1 до N.

Решение:

1. Генерация N случайных чисел;Гауссово или равномерное ...
2. Сортировать их;сохранить индекс (т. е. расположение каждого значения в списке)
3. Индекс сортировки - это ваш список.

В Matlab:

z = rand( [N 1] );
[dummy iz] = sort(z);

% ваш список.

Answer 2

Если у вас нет веских причин, вы не хотите изобретать псевдослучайное поколение. Вполне возможно, что-то не так. Я бы предложил начать с массива с A [i] = i

затем сделайте это:

for (i=0; i< n; i++) {
  j = random_number_between(i,n-1);
  swap(A[i],A[j]);
}

Редактировать Это в ответ на комментарии ниже:

Насколько случайным вы хотите, чтобы последовательность была. Обратите внимание, что неотъемлемой информацией в случайно выбранной перестановке является log (n!), Которая где-то близка к n ​​/ e битам. Таким образом, вам нужно генерировать столько случайных битов. Теперь, так как вы хотите, чтобы эти много случайных бит хранились где угодно, я думаю (больше похоже на интуицию, чем на математическое доказательство), было бы трудно сделать действительно случайную перестановку без такого большого количества памяти).

Но если вам просто нужна последовательность, которую нелегко реконструировать, вы можете просто объединить несколько функций 1: 1 одну за другой. На ум приходят две вещи: - сохранить счетчик i для последовательности, которая идет от 0 до N-1.

• do log_2 (N / 2) бит переворачивается на i, где биты для перестановки выбираются случайным образом при запуске последовательности.

• генерирует случайную перестановку по log_2 (N) битам в начале последовательности, используя вышеуказанный метод, а затем меняет местами биты в приведенном выше результате.

• Найдите случайное число r1, которое является относительным простым числом к ​​n at, и другое случайное число r2 между 0 и n-1. Ваш i-й номер = r2 ^ r% n.

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

Одна вещь, которая приходит на ум, это то, что если ваш диапазон равен 0..N-1, просто найдите большое число P, относительное простое число к N, и выберите другое случайное число