洗牌算法的背景
洗牌算法（Fisher-Yates shuffle) 由Ronald Fisher 和 Frank Yates 提出，他解决的问题为给定一些元素，如何等概率的生成一个序列。打个比方，扑克牌有54张牌，那么共有54！种排序方法，如何等概率的挑选其中的一种了？如果使用哈希表的方法，需要花费的空间复杂度为O(n!)，这肯定是不能容忍的。
洗牌算法的思想
洗牌算法巧妙的将等概率生成序列问题转化为使得每个元素出现在每个位置是等概率的。既然每个元素都能等概率的出现在每个位置，那么这个排列可以说是公平的。而实现它的方法异常简单：假设该序列有n个元素，将最后一个元素和前面任意n-1个元素数中的任意一个进行交换，之后倒数第二个元素和前面任意n-2个元素中的任意一个进行交换，依次迭代。如图所示：
接下来对洗牌算法进行证明。
洗牌算法的证明
将其转化为数学问题：
给定一个n个元素的序列，对于任意第i号的元素它出现在第j个位置的概率都为\(\frac{1}{n}\) 。
为了便于理解，先假设这个序列是自然数排列，即: 1,2,3,4,5,6…… n-2,n-1,n 总共n个元素。首先验证特殊性，先假定i=2，j=n。那么根据洗牌算法，它会等概率的选择前面n个元素中的一个，然后与第n号位置中的元素进行交换，这里的选择元素包括了第n个位置。于是2出现在第n号位置的概率为：\(\frac{1}{n}\)
那么对于j=n-1了，这需要 2 没有在第一次被选中并进行交换，然后计算2与第n-1号位置进行交换的概率。这是一个条件概率，用数学表达式可以写做：P(B={2出现在n-1号位置}|A={2号元素在第一次交换中未被选中})。计算得到：\(\frac{n-1}{n} * \frac{1}{n-1} = \frac{1}{n}\)
根据上面进行推导，若i能出现在第j号位置，那么说明在前n-j次选择中都没有被选中。计算出前n-j次未被选中的概率在乘以第n-j+1次被选中的概率。
c = n-j 当c>0 时:
前n-j次未被选中概率：
\[P_{1}=\prod_{k=1}^{c}\frac{n-k}{n-k+1}\]在第n-j+1次被选中的概率： \(P_{2}=\frac{1}{j}\)
相乘得到概率为：
\[P = P_{1} * P_{2} = [\prod_{k=1}^{c}\frac{n-k}{n-k+1}]*\frac{1}{j}=\frac{n-1}{n}*\frac{n-2}{n-1}...\frac{j}{j+1}*\frac{1}{j}=\frac{1}{n}\]当c =0 时，即有且只有j=n，不存在P1的情况，此时 \(P = P_{2} = \frac{1}{n}\)
于是元素i出现在任意位置的概率为 \(\frac{1}{n}\)得证。
这里使用假设检验法，更加简单：
第i号位置的元素出现在第n号位置的概率为：\(\frac{1}{n}\)
第i号位置的元素出现在第n-1号位置的概率为：\(\frac{n-1}{n} * \frac{1}{n-1}=\frac{1}{n}\)
假设第i号位置的元素与前第j-1号位置交换的概率都为：\(\frac{1}{n}\)
第i号位置的元素与第j号位置交换的概率为：\([\frac{n-1}{n}*\frac{n-2}{n-1}*\frac{n-3}{n-2}*...*\frac{j}{j+1}]*\frac{1}{j}=\frac{1}{n}\)
于是得证。
洗牌算法的简单程序
这里使用Python 进行编写。
from random import randinit
def shuffle(input_list):
length = len(input_list)
i=length
tmp=0
while(i>0):
swap_num = randint(0,i-1)
tmp=input_list[swap_num]
input_list[swap_num]=input_list[i-1]
input_list[i-1]=tmp
i-=1
return input_list
