Какая функция псевдослучайно переупорядочивает ровно N элементов?

Question

Имея натуральные числа от 1 до N (N около 1e7), я мечтаю о функции, которая бы переупорядочивала набор таким образом, который определяется довольно коротким набором параметров, по сравнению с диапазоном значений.

За N = 2^i - 1 это может быть просто немного переупорядочить, таким образом, набор только i значения 0..i определяет мутацию.

Я ищу такой же красивый способ, применимый к произвольной N.

---

Пример переупорядочения битов. 8 значений: 0..7 кодируются 3 битами: 000 – 111, Чтобы изменить порядок, я сохранил новую позицию каждого бита. Взять массив [0,1,2] и случайным образом изменить его порядок, а затем сохранить результат в качестве ключа перестановки. Т.е. [1,0,2] переупорядочим 8 значений следующим образом:

   210   201   
0: 000 - 000 :0
1: 001 - 010 :2
2: 010 - 001 :1
3: 011 - 011 :3
4: 100 - 100 :4
5: 101 - 110 :6
6: 110 - 101 :5
7: 111 - 111 :7

Answer 1

Простой способ не использовать память - умножить каждое число на константу, взаимно простую с N, а затем вычислить остаток от деления на N следующим образом (пример в Java):

static int reorder(int input, int N) {
    // 15485863 is prime, thus coprime with any lesser N
    return (int) ((input * 15485863L) % N);
}

Тестирование с N = 10345560:

public static void main(String[] args) {
    int N = 10345560;
    int[] source = IntStream.range(0, N).toArray();
    int[] reordered = IntStream.of(source).map(i -> reorder(i, N)).toArray();
    // Check that all reordered numbers are within 0..N-1
    assert IntStream.of(reordered).allMatch(i -> i >= 0 && i < N);
    // Check that all numbers are different
    assert IntStream.of(reordered).distinct().count() == N;
}

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

Недостатком является то, что для предоставленного параметра вы должны проверить, что он взаимно прост с N, и отклонить или скорректировать его, если это не так.

Answer 2

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

Я хотел бы предложить, что все, что вам нужно сделать, это

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

Answer 3

Не совсем уверен, что я понимаю ваш вопрос, но вы можете просто пройтись по числам от 1..N, и для каждого шага i генерировать псевдослучайное число j в диапазоне 1..N, а затем поменять местами i и j,