1

我想生成an 的排列，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;
}

问题：
是否有可能减少用于生成排列的随机数的总数？

4

3 回答 3

4

如果有人改进Knuth shuffle，我会感到惊讶。是 O(n)。

它需要 O(n) 个随机数，这对我来说还不够。

该引文声称使用 O(n log n) 算法。

我们都希望看到 O(log n) 或 O(1)。

O(log n) 算法通常依赖于“分而治之”的二分法，这让人想起切割甲板并划分每一半。

但我不禁想到，如果可以使用更快的算法，Knuth 就会找到它。

于 2009-11-14T15:47:24.973 回答
2

一个长度为 n 的序列有 n! 排列。如果每个排列都需要是可能的，那么每个排列都必须有一个可能的随机数序列。

要随机排列长度为 n 的数组，您可以从 1..n 范围内生成一个随机数！均匀随机。这标识了一个排列，然后您可以应用它。

您可能会改进您的问题以询问需要多少随机位。通过相同的论点，这将是 log(n!)。为了让您了解该函数的渐近行为，请考虑：

让 n > 3：

n = log(2^n) < log(n!) < log(n^n) = n * log(n)

所以 n 个随机位是不够的（对于 n > 3）。事实上，可以证明 log(n!) 不在 O(n) 中。

于 2009-11-14T16:44:39.993 回答
1

我能想到的唯一可能的优化是使随机数生成器更快。一个简单的解决方案是首先生成随机整数：

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) 限制。

于 2009-11-14T16:13:10.710 回答