洗牌算法

wayne

一副扑克牌有54张牌，有两种洗牌算法：

1. for(int i=0;i<n;++i)
   
2. {
   
3.         swap(a[i],a[random(1,n)]);
   
4. }
   

复制代码

1. for(int i=0;i<n;++i)
   
2. {
   
3.         swap(a[i],a[random(i,n)]);
   
4. }
   

复制代码

大家分别讨论下 其 概率分布，貌似计算不是那么的显然呢。

mathe

伪代码写的不对，但是能理解意思。第一种置换出$n^n$个结果，分给n!类，比例不能均匀。第二种显然每操作一轮，增加一个位置元素确定结果，其取值是均匀的，所以最终是均匀分布的

dianyancao

第一个算法：swap(a[i],a[random(0,n-1)]);
对于每种牌面的概率似乎也是等可能的

因为当交换a[i]和a[j]时，a[i]和a[j]取每张牌的概率都为1/n
第i次交换a[i-1]和a[j]时，总是使a[i-1]和a[j]取每张牌的概率都为1/n
所以循环完毕，将使每个a[i]取每张牌的概率都为1/n,
即各种扑克牌顺序出现的概率为等可能的

因此当试验次数m为n!的整数倍时，可以让各种扑克牌顺序等可能发生

dianyancao

上面的算错了，第一个洗牌算法产生的扑克牌顺序依赖于未洗牌前的扑克牌顺序
第i次交换a[i-1]和a[j]时，只是是使a[i-1]取每张牌的概率为1/n，a[j]取每张牌的概率和未洗牌前的扑克牌顺序有关

第一个算法产生的每个置换是等可能的，所以按各种扑克牌顺序n!分类，不能使每个类别的概率相等
如果试验次数趋于无穷大，是否可以使得每个类别的概率差值趋于0呢？

yy31742

受教了！！！！