Java-перестановки с наименьшим количеством возможных случайных чисел

Question

Я хочу, чтобы сгенерируйте перестановку из одного array a и я не хочу использовать служебные функции, такие как java.util.Коллекции().
Перестановки должны быть рандомизированный и каждая перестановка должна быть возможной - но нет необходимости в равномерно распределенной вероятности.

Следующий код достигает этого - но при низкой производительности :

// array holding 1,...,n
// initialized somewhere else
int[] a = new int[N];

for (int i = 0; i < a.length ; i++) {
     int r = (int) (Math.random() * (i+1));     
     swap(r,i,a);
  }

private static void swap(int j, int k, int[] array){
      int temp = array[k];
      array[k] = array[j];
      array[j] = temp;
}

Вопрос:
Есть ли какой-либо шанс уменьшить общее количество случайных чисел, используемых для генерации перестановки?

Answer 1

Я буду удивлен, если кто-нибудь улучшит Кнут перетасовывает.Это O(n).

Для этого требуется O (n) случайных чисел, чего для меня недостаточно.

Эта цитата утверждает, что используется алгоритм O(n log n).

Мы все хотели бы увидеть see O(log n) или O (1).

Алгоритмы O (log n) обычно зависят от деления пополам по принципу "разделяй и властвуй", что напоминает разрезание колоды и деление каждой половины.

Но я не могу отделаться от мысли, что если бы был доступен более быстрый алгоритм, Кнут нашел бы его.

Answer 2

Последовательность длины n имеет n!перестановки.Если каждая перестановка должна быть возможной, для каждой из них должна быть возможная последовательность случайных чисел.

Таким образом, чтобы случайным образом переставить массив длиной n, вы можете сгенерировать одно случайное число из диапазона 1..n!равномерно наугад.Это определяет единственную перестановку, которую затем вы можете применить.

Вы могли бы улучшить свой вопрос, чтобы спросить, сколько случайных битов необходимо.По тому же аргументу это будет log(n!).Чтобы дать вам представление об асимптотическом поведении этой функции, рассмотрим:

Пусть n > 3:

n = логарифм (2^n) < журнал (n!) < log(n^ n) = n * log(n)

Таким образом, n случайных битов может быть недостаточно (для n > 3).На самом деле, можно доказать, что log(n!) не входит в O(n).

Answer 3

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

import java.util.Random;
Random rand = new Random();

for (int i = 0; i < a.length ; i++) {
    swap(rand.nextInt(i+1), i, a);
}

...

В качестве альтернативы вы можете изобрести более быстрый способ генерации более или менее случайных чисел (равномерно распределенных или нет, в соответствии с вашими потребностями).Однако вы никак не сможете преодолеть ограничение O (n).