洗牌算法

新的方案是从牌套里随机找到两个位置，将其位置的牌交换。重复若干次后，便可以将牌洗乱。这里最关键的是需要找到一个合适的重复次数。

这个问题首先需要定义什么叫作“洗乱”。

我随便给出了一个定义：在洗牌过程中，任意一张牌不被抽到交换的概率小于 1/1000 。（这个定义不太符合直观感觉，这个下面会讨论）

简单的列出方程：( (n-2)/n ) ^ m <=1/1000 得到 m >= -3* ln 10 / ln (1-2/n)

对于 52 张牌，大约是 176 次。

之后，另一个同事给了我另一个方案。产生 N 个不易发生碰撞的随机数，比如 (0,1) 的浮点数，或是 [0,4G) 的整数。将这些数字排序，则可以得到一个被打乱次序的序列。

这个方案看起来更好，因为更接近洗乱牌的目的。我重新给一个“洗乱”的定义：每张牌在每个位置出现的概率相同。

反过来，我想知道前面我给出的交换法洗牌有多接近它。

要得到严格的数学分析似乎很困难。偷懒 google 了一下，原来好多人研究过类似问题了。看这里：

http://mathworld.wolfram.com/Shuffle.html

从这个链接找过去，有一篇论文 。它讨论了另一种类似的洗牌方法，即第一次把第一张和随机一张牌交换，第二次把第二张和随机一张牌交换…… 重复做 N 次。

当 N 大于等于 18 时，用这个方法洗牌后，居然恒等排列（identity permutation）是最有可能出现的。（所谓恒等排列大概是指第 n 张排在第 n 个位置）。论文太长没精力读，不过这个结论还真是让人惊奇啊。

还有你自己实现的那个也不咋地， 最简单的
for(int i=0;i<n;i++){
swapArray(i, random(i,n))
}

算法导法里的一个算法：
function randomize(A)
n=A.length
for i=1 to n
j=random(i,n)
swap A[i],A[j]