Как задать перемешивание массива относительно коротким числом параметров?

Question

[Сергей Соколов]

Есть ровно N натуральных чисел подряд от 1 до N. Их нужно перемешать, псевдослучайно. Так, чтобы это перемешивание определялось относительно небольшим числом параметров (относительно числа значений).

Понятно, что можно просто использовать массив из N чисел, случайно перемешанный.

Для N = 2^i я использовал перестановку порядка битов – требовалось сохранить всего i чисел от 0 до i, чтобы закодировать перемешивание.

Теперь ищу похожее по «красоте» функциональное решение для произвольного N.

Answer 1

[Андрей]

Наиболее быстрым в Вашей постановке мне кажется использование ГПСЧ на основе
линейного конгруэнтного метода с условиями:
1) m=2^L (где L - округл.вверх от log2(N+1))
2) a mod 4 = 1
3) c mod 2 = 1
(это приведет к перебору всех чисел от 0 до m-1 строго по одному разу)
и игнорированием всех чисел, больших чем N
(a, c, X0 - параметры, определяющие перестановку).

Вот пример работы для N=21 (m=32)

A=25 C= 3 X0=22: 9;4;7;18;5;3;14;1;10;6;20;2;21;16;19;17;12;15;13;8;11;
A= 9 C= 9 X0=17: 2;5;15;16;10;3;4;13;1;18;11;12;21;6;9;19;20;14;7;8;17;
A=17 C=21 X0= 2: 17;11;16;5;10;4;19;13;18;7;12;1;6;21;15;20;9;14;3;8;2;
A=17 C=25 X0=12: 5;14;7;16;9;18;11;20;13;15;17;19;21;2;4;6;8;1;10;3;12;

Есть методы с сортировкой, но они потребуют объемов памяти, равных N. Могу описать, если интересно ...
Кстати, каков порядок и верхняя граница N ?

Comments

[Сергей Соколов]

N порядка 1e7

[Андрей]

Ну метод естественно остается в силе, только нужно следить за переполнением при умножении