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

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

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

// 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;
}

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

Источник

3 ответа

Решение

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

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

Эта цитата требует алгоритма O (n log n).

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

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

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

Источник

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

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

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

Пусть n> 3:

n = log (2 ^ n)

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

Источник

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

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).

Источник
Другие вопросы по тегам