隨機排序 - Fisher Yates，爲什麼不能找到0和N-1之間的隨機數？

Question

在學習Shuffle排序時，我學習了Fisher Yates解決方案。它循環0到數組長度，並找到一個介於0（包括）和循環索引（包括）之間的隨機數字，並且找到不是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）返回0之間的收益隨機數和I（包括兩端）

Answer 1

這是因爲你不能用等概率生成每個序列與你選擇0到n-1之間的r的方法。

示例： 考慮集合{a，b，c}的n = 3 總可能結果= 3！ 現在考慮完美隨機發生器，可能導致交換，這將產生，其對應的混洗集是原樣>

1. 0 1 2 {A，B，C}
2. 0 2 1 {A，B ，C}
3. 1 0 2 {A，b，C}
4. 1 2 0 {A，C，b}
5. 2 0 1 {b，A，C}
6. 2 1 0 {一，b，c}

顯然沒有涵蓋所有的結果，實際執行Fisher Yates將不會這樣。

Answer 2

如果你只從0選擇N-1，那麼你可以不會選擇最後一個號碼在數組中。因此它不是完全隨機的。

您可以預測最後一個數字至少會明顯不合適。

我知道這並不意味着你可以預測整個序列，但它確實意味着系統中沒有完全的隨機性。