C#實現的洗牌算法

我們先看一下紙牌游戲。一幅紙牌由 52 張不同的紙牌組成，發牌時必須產生不重復的紙牌，而且洗牌過程必須公平，即 52! 中紙牌順序應該等概率出現。很明顯這種隨機排列所產生的隨機數必須均勻分布且獨立。由此代碼如下：

1. using System;
2. using System.Diagnostics;
3.  
4. namespace Lucifer.CSharp.Sample
5. {
6.     class Program
7.     {
8.         static void Main(string[] args)
9.         {
10.             //初始化牌局
11.             int[] array = new int[52];
12.             for (int i = 0; i < array.Length; i++)
13.             {
14.                 array = i;
15.             }
16.  
17.             //洗牌
18.             Permute<int>(array);
19.  
20.             //驗證牌局
21.             for (int i = 0; i < array.Length; i++)
22.             {
23.                 var value = array;
24.                 for (int j = 0; j < array.Length; j++)
25.                 {
26.                     if (j == i) continue;
27.                     Debug.Assert(array[j] != value);
28.                 }
29.             }
30.         }
31.  
32.         static void Permute<T>(T[] array)
33.         {
34.             Random random = new Random();
35.             for (int i = 1; i < array.Length; i++)
36.             {
37.                 Swap<T>(array, i, random.Next(0, i));
38.             }
39.         }
40.  
41.         static void Swap<T>(T[] array, int indexA, int indexB)
42.         {
43.             T temp = array[indexA];
44.             array[indexA] = array[indexB];
45.             array[indexB] = temp;
46.         }
47.     }
48. }

代碼示例中的 Permute<T>(T[] array) 方法產生一個隨機序列。第一個循環用 1, 2, 3, …, N 初始化該序列。第二個循環完成一次隨機洗牌。在該循環的每次迭代中，我們講 array[j] 的值於數組位置在區間[0, j)之間的某個元素相交換(也可能不交換)。

然而，我們要問的是 Permute<T>(T[] array) 方法產生的所有排列等概率嗎？

若根據該算法，答案為是。因為一共有 N! 種可能的排列，而 Swap<T>(array, i, random.Next(0, i)); 這一句 N-1 次調用 Next 方法出現的不同結果也是 N! 種。但是，事實上答案為否，並非所有排列都是等概率。問題就出在可愛的偽隨機數數生成器(Pseudo-Random Number Generator)上。PRNG 的隨機性很大程度上限制了隨機序列的隨機性。所以，上述代碼需要一個更好的偽隨機數數生成器以使實際與理論更加相符。但是好的 PRNG 往往伴隨著性能的下降，比如 Mt19937 隨機化算法。