如何stdrandom洗牌方法效果

Question

public static void shuffle(Object[] a) { 
    int N = a.length; 
     for (int i = 0; i < N; i++) { 
      int r = StdRandom.uniform(i + 1);  
      exchange(a, i , r) 
     } 
    } 

以上是從StdRandom類的方法在Java編碼。我想知道爲什麼stdRandom.uniform（i + 1）它在0和i之間，而不是在0和（N-1）之間。

Answer 1

簡短的回答是介於0和N-1不創建均勻地隨機分佈。

當設計一個洗牌，要確保值配置的所有可能的隨機組合是同樣可能，以及0到N-1使一些成果比其他人更容易。

有關更詳細的討論，請參閱Shuffling algorithm analysis。

Answer 2

洗牌算法工作就像你，如果你用一頂帽子洗牌。將所有卡片鬆散地扔進帽子裏。抽出一張隨機卡，將它放在位置0，然後放在位置1，等到帽子空了，所有的地方都被填滿了。

在算法當i正在填充時，其餘的數組（位置i + 1，i + 2，... N-1）是帽子。 exchange從帽子中拉出一個隨機項目，並將其放在需要的位置。這是在位置i向上移動，這樣它仍然在帽子中的項目。它位於帽子的位置並不重要，因爲下一個隨機數字將以相同的概率選取所有帽子位置。

希望這直觀的解釋是有道理的......