具有最少随机数的 Java 排列

Question

我想生成一个 array a 的排列而且我不想使用实用功能，例如 <a href="http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#shuffle%28java.util.List%29" rel="noreferrer noopener nofollow">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;
}

问题:
是否有机会减少用于生成排列的随机数总数？

Answer 1

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

It takes O(n) random numbers, which is not sufficient for me.

This citation要求 O(n log n) 算法。

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

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

但我忍不住想，如果可以使用更快的算法，Knuth 应该会找到它。