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

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

1 голос
/ 14 ноября 2009

Я хочу сгенерировать перестановку из array a, и я не хочу использовать служебные функции, такие как <a href="http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#shuffle%28java.util.List%29" rel="nofollow noreferrer">java.util.Collections()</a>.
Перестановки должны быть рандомизированными , и каждая перестановка должна быть возможной, но нет необходимости в равномерно распределенной вероятности.

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

// 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 ]

4 голосов
/ 14 ноября 2009

Я буду удивлен, если кто-нибудь улучшит Knuth shuffle . Это O (n).

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

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

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

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

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

2 голосов
/ 14 ноября 2009

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

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

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

Пусть n> 3:

n = log (2 ^ n)

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

1 голос
/ 14 ноября 2009

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

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

...