2014-08-24
**问题描述:**有n张牌和n个位置,如何让每张牌出现在每个位置的可能性是1/n?
其实,可以把这个算法分成两个目标:
- 目标1:得到的结果看起来是随机的。
- 目标2:某张牌出现在某个位置的可能性是1/n;某个位置上出现某张牌的可能性是1/n。
要解决这个问题,有一点需要注意,牌一定要看成乱序的,牌在开始时候的顺序不应该影响洗牌的结果。
好了,现在我们手中有四张牌:a、b、c、d。
方法1
从n张牌中,随机抽出1张牌,放在位置0;从剩下的牌中随机抽出一张牌,放在位置1,如此循环,直到没有剩下的牌。
ruby实现如下:
运行几次的结果:
这个解法在数学上很容易证明其满足目标1和目标2,也可以使用统计的方式证明其正确性。以牌a
为例,记录其在分别位置0、1、2、3出现的次数,若这些次数差不多,就没问题了。 下面测试方法1:
运行结果是:
这是很令人满意的结果。
改进方法1
在测试时可以发现方法1有一个严重的问题,即每调用一次shuffle01(),arr会被置空,且会生成一新的数组对象arr2。一个比较好的方法是在arr内部进行调整,如下:
测试程序:
某次运行结果如下:
这个测试程序的运行速度要比方法1的测试程序快一些。
方法2
这个思路和方法1差不多:从n张牌中,随机抽出1张牌,放在位置n-1;从剩下的牌中随机抽出一张牌,放在位置n-2,如此循环,直到没有剩下的牌。该算法同样满足目标1和目标2。
代码:
测试:
测试程序的某次运行结果:
方法3
把牌最开始的摆放顺序认为是有序的。随机生成两个在0和n-1之间(包括这两个数)的整数,将这两个位置的牌调换swap,如此循环操作n次。 代码如下:
测试代码如下:
注意,这次把类ShuffleTest
修改得更通用了一些。测试程序的某次运行结果如下:
这个程序自然满足目标1,同时看起来满足目标2,但实际上并不满足目标2。这个需要证明一下(我没什么头绪,在stackoverflow问了下,找到了答案,问题地址是:Is this shuffle algorithm right?):
对于a、b、c、d这四张牌,共有4!=24种排列。shuffle03!
共有4次循环,每次循环中生成两个0..3
的随机数(4中可能性);转换一下说法就是,8个随机数,每个随机数随机取四个值中的一个,由此共有84=4096个排列,这也意味着总体来说是4096个等概率的排列,每一个这样的排列必然对应个牌的24种排列之一。4096无法整除24,即无法平均分配到24种牌的排列中。所以,无法满足目标2。
给出答案的牛人之后又补充了一下更通俗的证明: 假设现在手中四张牌在初始时候排列为a、b、c、d,现在之考虑c和d。shuffle03!()
会执行4次循环,每次循环中随机选取两张牌(这两张牌可能是同一个,相当于有放回的抽样),调换这两张牌的位置。可知,一次循环里,有16个抽样结果(a,a)、(a,b)、(a,c)、(a,d)、(b,a)等,其中(a,b)
代表a和b调换位置,这16个结果是等概率的。在这其中有(c,d)
和(d,c)
,即c和d调换位置的方式有两种。所以在一次循环中c和d调换位置的概率是1/8
,不调换位置的可能性是7/8
。由于有4次循环,这就是一个二项分布,故总体上来说:
- c和d调换位置这一事件调换位置的次数出现0次的概率是:(7/8)4 ≈ 58.6%
- c和d调换位置这一事件调换位置的次数出现1次的概率是:4 × (1/8) × (7/8)3 ≈ 33.5%
- c和d调换位置这一事件调换位置的次数出现2次的概率是:6 × (1/8)2 × (7/8)2 ≈ 7.18%
- c和d调换位置这一事件调换位置的次数出现3次的概率是:4 × (1/8)3 × (7/8) ≈ 0.68%
- c和d调换位置这一事件调换位置的次数出现4次的概率是:(1/8)4 ≈ 0.02%
所以最终牌c在牌d前面的概率是58.6% + 7.18% + 0.02% ≈ 65.8% ,牌c在牌d后面的概率是33.5% + 0.68% ≈ 34.2% 。很明显,shuffle03!()
有问题。
如果循环的次数增加,则洗牌的效果会更好,即牌c在牌d前面的概率和牌c在牌d后面的概率越相近。
ruby自带的shuffle
python也自带shuffle方法:
其他方法
维基百科上关于洗牌算法的内容:Fisher–Yates shuffle。
Shuffling algorithm analysis给出了一个方法。在如何测试洗牌程序中也给出了更多的有趣但可能不对的方法,评论中也给出了一些方法。
洗牌算法与取样问题
这段内容是在2014-08-25号补充,我在《编程珠矶》第12章“取样问题”看到了洗牌算法的应用,记录一下。另外,蓄水池算法也可用于取样问题。
现有10个元素,需要从中随机的挑选2个作为样本,这就是一个取样问题。
我们先想一个简单的方法:
也可以是使用洗牌算法来巧妙的解决该问题,我们将0到9这10个数字打乱,前两个数字即为样本的位置:
实际上,此时对于shuffle01!()
函数而言,其内的循环执行两次即可: