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

Question

Я прочитал пару постов здесь о генерации случайной последовательности без повторов (например Create Random Number Sequence with No Repeats) и решил реализовать его для моей собственной потребности

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

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

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

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

Благодаря

Max

Answer 1

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

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

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.

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

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

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

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

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

Answer 2

Проблема:

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

Решение:

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

В Matlab:

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

% из- Ваш список.