問題：給定一個有序序列1~n，要你將其完全打亂，要求每個元素在任何一個位置出現的概率均為1/n。

解決方案：依次遍歷數組，對第n個元素，以1/n的概率與前n個元素中的某個元素互換位置，最后生成的序列即滿足要求，1/n的概率可通過rand() % n實現。見如下程序：

void swap(int* p, int* q)

{

????int tmp = *p;

????*p = *q;

????*q = tmp;

}

?

void shuffle(int *arr, int n)

{

????int i;

????for(i = 0; i < n; i++) {

????????int idx = rand() % (i + 1); //選取互換的位置

????????swap(&arr[idx], &arr[i]);

????}

}

?

?使用數學歸納法證明：

l??當n=1時，idx必為0，所以元素arr[0]在任何一個位置的概率為1/1，命題成立。

l??假設當n=k時，命題成立，即n=k時，原數組中任何一個元素在任何一個位置的概率為1/k。

?則當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。

?

擴展：一道google面試題

給定一個未知長度的整數流（數目大于1000），如何從中隨機選取1000個隨機數。

?

解決方法：

l??定義長度為1000的數組，對于數據流中的前1000個關鍵字，顯然都要放到數組中。

l??對于數據流中的的第n（n>1000）個關鍵字，則這個關鍵字被隨機選中的概率為?1000/n。故以?1000/n?的概率用這個關鍵字去替換數組中的一個。這樣就可以保證所有關鍵字都以?1000/n的概率被選中。對于后面的關鍵字都進行這樣的處理，這樣就可以保證數組中總是保存著1000個隨機關鍵字。

?

注：以1000/n的概率選擇一個數替換，可通過rand() % n實現，則這個數被替換到前1000個位置中的概率為1000/n。

轉自：http://blog.chinaunix.net/uid-20196318-id-216658.html

轉載于:https://www.cnblogs.com/freeopen/p/5482894.html

總結

以上是生活随笔為你收集整理的随机洗牌的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。