## 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)