我想生成一个 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;
}
问题:
是否有机会减少用于生成排列的随机数总数?
最佳答案
如果有人改进 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 应该会找到它。
关于具有最少随机数的 Java 排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1734594/