一个简单有效的洗牌算法

核心提示：装配脑袋兄在某个帖子中指出了一种有意思的洗牌算法，博主按照他的思路写了另外一种洗牌算法，一个简单有效的洗牌算法，下面是该洗牌算法的思路：我们先看一下纸牌游戏，一幅纸牌由 52 张不同的纸牌组成，但不保证其能在商业化项目中得以正确实践，我记得云风兄在他的博客上也曾经讨论过洗牌算法，发牌时必须产生不重复的纸牌，而且洗牌过程

装配脑袋兄在某个帖子中指出了一种有意思的洗牌算法，博主按照他的思路写了另外一种洗牌算法。下面是该洗牌算法的思路：

我们先看一下纸牌游戏。一幅纸牌由 52 张不同的纸牌组成，发牌时必须产生不重复的纸牌，而且洗牌过程必须公平，即 52! 中纸牌顺序应该等概率出现。很明显这种随机排列所产生的随机数必须均匀分布且独立。由此代码如下：

using　System;
using　System.Diagnostics;

namespace　Lucifer.CSharp.Sample
{
　　class　Program
　　{
　　　　static　void　Main(string[]　args)
　　　　{
　　　　　　//初始化牌局
　　　　　　int[]　array　=　new　int[52];
　　　　　　for　(int　i　=　0;　i　<　array.Length;　i++)
　　　　　　{
　　　　　　　　array[i]　=　i;
　　　　　　}

　　　　　　//洗牌
　　　　　　Permute<int>(array);

　　　　　　//验证牌局
　　　　　　for　(int　i　=　0;　i　<　array.Length;　i++)
　　　　　　{
　　　　　　　　var　value　=　array[i];
　　　　　　　　for　(int　j　=　0;　j　<　array.Length;　j++)
　　　　　　　　{
　　　　　　　　　　if　(j　==　i)　continue;
　　　　　　　　　　Debug.Assert(array[j]　!=　value);
　　　　　　　　}
　　　　　　}
　　　　}

　　　　static　void　Permute<T>(T[]　array)
　　　　{
　　　　　　Random　random　=　new　Random();
　　　　　　for　(int　i　=　1;　i　<　array.Length;　i++)
　　　　　　{
　　　　　　　　Swap<T>(array,　i,　random.Next(0,　i));
　　　　　　}
　　　　}

　　　　static　void　Swap<T>(T[]　array,　int　indexA,　int　indexB)
　　　　{
　　　　　　T　temp　=　array[indexA];
　　　　　　array[indexA]　=　array[indexB];
　　　　　　array[indexB]　=　temp;
　　　　}
　　}
}

代码示例中的 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 随机化算法。

题外话：博主在实际代码运行中，发现上述代码能很好的完成洗牌算法要求，但不保证其能在商业化项目中得以正确实践。我记得云风兄在他的博客上也曾经讨论过洗牌算法，有兴趣的兄弟可以搜索一番。