问题背景：
有一副牌假设有N张，请设计一个随机洗牌算法。
解决方案：
这里只给出一个可以使用数学证明每张牌出现在任何位置概率为1/N的算法。
Poker[N]
for (i = 0; i < N; ++i)
{
k = rand() % ( i + 1)
if (i != k)
{
switch(Poker[k], Poker[i]);
}
}
分析：
第一次取第一张牌(i=0)保持位置不变。第二次取第二张牌(i=1)，随机生成0-1的随机数k，如果随机生成数不为1，，则交换下标为k和i的牌，否则不进行交换。
假设现在取第Z张牌(i = Z – 1)， k= rand()%Z, 如果k!=i则交换下标为k和i的两张牌。
这个算法粗看起来有点像蓄水池抽样的操作方法。这样我们来看一下每张牌出现位置的概率。
第一次计算时第一张牌(i=0)出现在第一个位置的概率为1。
第二次计算时第二张牌(i=1)很明显出现在两个位置中的概率都是1/2。
我们就是要证明第Z（Z<=N)次计算时每张牌出位位置的概率为1/Z。
下面采用归纳法来证明。
1. 很明显Z=1时结论成立。
2. 假设当Z = K时结论也成立。
当Z=K+1时，易知第Z张牌出现在任意位置的概率为1/Z。
前K个数能够保留当前位置的概率为（1 – 1/(K+1)), 那么任意一张牌出现在任意位置的概率为(1/K) *（1 – 1/(K+1)) = 1/(K+1)。
3. 同样当Z=N时该算法也成立。
版权声明：本文为博主原创文章，未经博主允许不得转载。
而消极的人则在每个机会都看到某种忧患。
