STL经典算法集锦<七>之随机洗牌(random_shuffle)

最后更新于:2022-04-01 07:30:46

## STL经典算法集锦<七>之随机洗牌(random_shuffle) 将一个数组中的元素序列打算顺序进行重排,并需要保证重排后的每一种结果是等概率且随机的。下面的两种算法哪一种是正确的?(注:random(a,b)返回一个a~b的随机整数) 1. for i=1 to n do swap( a[i], a[random(1,n)] ); 2. for i=1 to n do swap( a[i], a[random(i,n)] ); **解释:** 首先,1~n的序列打乱重排共有n!个不同的排列,且每种排列被选中的概率为1/N!,只有这样的算法才是等概率且随机的。   第一种算法将会产生n^n种情况,显然其中出现了重复的情况。那么会不会虽然出现重复,但每种排列重复的次数相同,所以算法依然是等概率且随机的呢?答案是,不会。 假设上述情况成立,则n^n必定n!整除。但是,绝大多数情况下,n!的质因子远多于n^n的质因子(即n的质因子)。根据Bertrand-Chebyshev定理,在n/2和n之间一定还有一个质数。这两个质数的乘积已经大于n了。搞了半天,第一种看似对称而美观的算法居然是错的!即对所有大于2的n,上述整除都不不可能的。   第二种算法是符合要求的随机洗牌算法。 使用数学归纳法证明: 1、当n=1时,所以元素arr[0]在任何一个位置的概率为1/1,命题成立。 2、假设当n=k时,命题成立,即原数组中任何一个元素在任何一个位置的概率为1/k。 3、则当n=k+1时,当算法执行完k次时,前k个元素在前k个位置的概率均为1/k。当执行最后一步时,前k个元素中任何一个元素被替换到第k+1位置的概率为:(1-1/(k+1)) * 1/k = 1/(k+1); 在前面k个位置任何一个位置的概率为(1-1/(k+1)) * 1/k = 1/(k+1);故前k个元素在任意位置的的概率都为1/(k+1)所以,对于前k个元素,它们在k+1的位置上概率为1/(k+1)。对于第k+1个元素,其在原位置的概率为1/k+1,在前k个位置任何一个位置的概率为:(1-k/(k+1)) * (1/k)=1/(k+1),所以对于第k+1个元素,其在整个数组前k+1个位置上的概率也均为1/k+1。  综上所述,对于任意n,只要按照方案中的方法,即可满足每个元素在任何一个位置出现的概率均为1/n。   解释完了洗牌算法的原理,那下面就是自己实现的random_shuffle的代码。 ~~~ void swap(int& a,int& b)//不要尝试用“抑或”运算完成元素的交换,详见抑或运算 { int temp=b; b=a; a=temp; } void randomShuffle(int array[], int len) { for(int i=1;i<len;i++) { int j=rand()%(i+1); swap(array[i],array[j]); } } ~~~ 注:本文解释部分参考了以下文章: [http://hi.baidu.com/wulei407/blog/item/b6ea451b6572f9fdaf513315.html](http://hi.baidu.com/wulei407/blog/item/b6ea451b6572f9fdaf513315.html) [http://blog.chinaunix.net/uid-20196318-id-216658.html](http://blog.chinaunix.net/uid-20196318-id-216658.html)
';