随机排序 - Fisher Yates，为什么我找不到 0 到 N-1 之间的随机数？

Question

在学习Shuffle排序的过程中，学习了Fisher Yates解法。它循环 0 到数组长度，并在 0（含）和循环索引（含）和 NOT 0 和 N-1 之间找到一个随机数。找到 0 到 N-1 之间的随机数不会给出随机解。但是我找不到相同的原因。

public static void sort(Comparable[] a){

    for(int i = 0 ; i < a.length ; i++){ 

        int r = StdRandom.uniform(i+1); 
        // why cant this be a.length

        exch(a, i, r);

    }
}

StdRandom.uniform(i+1) returns returns 0到i之间的随机数（包括）

Answer 1

如果你只select从0到N-1，那么你永远不能选择数组中的最后一个数字。因此它不是完全随机的。

你可以预测，至少最后一个数字肯定会错位。

我知道这并不意味着您可以预测整个序列，但这确实意味着系统中不存在完全随机性。

Answer 2

那是因为您无法通过在 0 到 n-1 之间选择 r 的方法以相同的概率生成每个序列。

示例：考虑集合 {a,b,c} 的 n=3 总可能结果 = 3！现在考虑完美的随机生成器，它将生成的可能交换结果及其相应的洗牌集为->

0 1 2 {a,b,c}
0 2 1 {a,b,c}
1 0 2 {a,b,c}
1 2 0 {a,c,b}
2 0 1 {b,a,c}
2 1 0 {a,b,c}

显然没有涵盖所有结果，Fisher Yates 的实际实施情况并非如此。

随机排序 - Fisher Yates，为什么我找不到 0 到 N-1 之间的随机数？

Shuffle sort - Fisher Yates, why cant I find random number between 0 and N-1?

sorting

random

shuffle