STL算法我实现之随机洗牌


将一个数组中的元素序列打算顺序进行重排,并需要保证重排后的每一种结果是等概率且随机的。下面的两种算法哪一种是正确的?(注: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]);
     }
}
# STL