返回信息流题目：编写一个函数，洗一副牌。要求做到完美洗牌，换言之，这副牌 52! 种排列组合出现的概率相同。假设给定一个完美的随机数发生器。
有一种解法是这样：假定有个方法shuffle()对n-1个元素有效，则先利用shuffle()打乱前n-1个元素的次序，然后，取出第n个元素，将它与数组中的元素随机交换。
代码如下：
bool shuffleArrayInteratively(int* a,int len)
{
if(a==nullptr || len<=0)
return false;
for(int i=1;i<len;i++)
{
//PerfectRand(i)的作用是随机生成一个大于等于0、小于等于i的整数，由出题者提供
int randnum=PerfectRand(i);
int temp=a[randnum];
a[randnum]=a[i];
a[i]=temp;
}
return true;
}
请问这种解法的数学原理是什么？为什么这样生成的 52！ 种排列组合概率是一样的？
这是一条镜像帖。来源：北邮人论坛 / cpp / #84542同步于 2014/12/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
【求助】一道面试题，关于洗牌的算法
en911
2014/12/1镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
只需要证明任意一种排列出现的概率是1/52!就可以了。可以从后面往前看，最后一张牌是从52里选一张，选中特定牌的概率是1/52,倒数第二张牌是从剩余的51张里选一张，概率是1/51，依次类推，任意一副牌排列出现的概率是1/52!，这中间有很多swap，但不影响概率。
【 在 en911 的大作中提到: 】
: 题目：编写一个函数，洗一副牌。要求做到完美洗牌，换言之，这副牌 52! 种排列组合出现的概率相同。假设给定一个完美的随机数发生器。
: 有一种解法是这样：假定有个方法shuffle()对n-1个元素有效，则先利用shuffle()打乱前n-1个元素的次序，然后，取出第n个元素，将它与数组中的元素随机交换。
: 代码如下：
: ...................
说得很明白，多谢。
【 在 gaoweiwei 的大作中提到: 】
: 只需要证明任意一种排列出现的概率是1/52!就可以了。可以从后面往前看，最后一张牌是从52里选一张，选中特定牌的概率是1/52,倒数第二张牌是从剩余的51张里选一张，概率是1/51，依次类推，任意一副牌排列出现的概率是1/52!，这中间有很多swap，但不影响概率。