2010年4月17日星期六

随机排列算法的一个证明[转载]

对n个元素的数组,一个极简单有效的随机排列算法如下所示:

for(int i = n-1; i > 0; i--){
swap(i,rand()%(i+1));
}

这个算法初看起来并不自然,但其实是很简单的。直观地看,排列过程中,数组分为两部分:排列就绪部分(长度为n-i)和候选元素部分(长度为i)。每次从候选元素部分随机取一元素(rand()%(i+1)),放到排列就绪部分头部,将所占据位置上原来的元素扔进候选元素部分。注意到,候选元素部分的顺序是无关紧要的,因为一个元素无论处于什么位置,下一次被选到的概率都是1/候选部分长度。因此为了算法复杂度低和简单起见,每次都将被占据位置的元素与被选到的元素交换(这两者有可能是同一元素)。简单地说,它的思想就是从一堆元素中随机选出一个来,再从剩下的元素里随机选择,直到选完为止。

严格证明的话,用数学归纳法是简单的,对n进行归纳即可。但好久不做数学题,头脑快生锈了,因此尝试一下复杂一些的证明,证明思想是对原位置i的元素进行跟踪。

定义一个函数:候选部分长度为n时,数组的第i个元素在算法结束后处于第k个位置的概率。

元素i第一次参与交换(即swap()的参数中出现了i)后,处于位置j(j=1..n)的概率有多大呢?有两种情况,第一种情况是i<=j,这时发生的事情就是第n-j+1次交换时,元素i与元素j发生了交换,如下图所示:

这个发生的概率是:P(元素i与元素n没有交换)*P(元素i与元素n-1没有交换)*...*P(元素i与元素j+1没有交换)*P(元素i与元素j交换) =

第二种情况,j<i,这时发生的事情就是第n-i+1次交换时,元素i与元素j发生了交换,如下图所示:

这个发生的概率是:P(元素i与元素n没有交换)*P(元素i与元素n-1没有交换)*...*P(元素i与元素i+1没有交换)*P(元素i与元素j交换)=

因此在两种情况下,元素i在第一次参与交换时,被换到位置j(j=1..n)的概率都是1/n。

因此有: ,m为i第一次参与交换后候选数组大小,m=1..n-1。

即元素i最终处于位置k的概率,等于第一次参与交换后处于位置j(j=1..n),之后再被换到位置k的概率。

由于 ,(1≤m≤n,1≤k≤n),即数组内总有一个元素j,最终处于位置k,因此

即位置i的元素最终处于任意位置k的概率都是 。由于算法只涉及元素的交换,因此产生的是数组元素的全排列,结合任意元素处于任意位置的概率相等可知产生任意排列的概率都是相等的(这一点结合条件概率可以证明),即满足均匀随机。


来自: http://hi.baidu.com/timeless/blog/item/23cfb7459c72e32fcffca395.html