我們在前幾節，介紹了一篇三種方案解決**如何生成位于0到n-1之間的k個不同的隨機順序的隨機整數？**[[請點擊](http://blog.csdn.net/utimes/article/details/8761541)]，本節則基于上述中，拓展如下所示的問題，然后，給出幾個方案。 ### 問題描述 產生[0, n) 范圍內不重復的隨機數。 ### 方案一：Knuth 的S方案 有一個結論：從r中等概率的選出s個，某一個被選中的概率為s/r。證明：從r中選出s個有C(r, s)種情況，其中C(r, s)表示組合。同理，若要選定某項比如t，則需要從生下的(r-1)項中，選擇(s-1)項，有C(r-1, s-1)種情況。則從r項中選擇s項，t被選中的概率為　P = C(r-1, s - 1) / C(r, s)　；另一方面有排列組合的性質知，C(r,s) = r!/( s! *(r-s)! )　則有 　　C(r - 1, s - 1) = (r-1)!/( (s-1)! * (r-s)! ) = s/r * r/s * (r-1)!/( (s-1)! * (r-s)! ) ??????????????????????????? = s/r * r*(r-1)! / ( s*(s-1)! * (r-s)!) = s/r * r!/( s! *(r-s)! ) = s/r * C(r, s) 故有P = s/r 偽代碼 ~~~ for i = [0, n) if bigrand()%r < s then print i --s; --r; ~~~ 例如n=5, m =2, 那么選第一個元素的概率就是2/5,如果選上了那么選第二個元素概率就是1/4，否則選擇第二個元素的概率就是2/4 ~~~ void gen_knuth(int n, int m){ for(int i = 0; i < n; i ++){ if(big_rand()%(n-i) < m){ cout << i; m--; } } cout<< endl; } ~~~ ### 方案二：Knuth 置換方法P 首先用一個數組順序存儲[0, n)的數據，然后隨機交換任意兩個下標的元素，最終取其最初的m個，記得到m個不同的隨機數。 ~~~ for i = [0, n) x[i] = i; for i = [0, m) swap(i, randint(i, n-1)) ~~~ ### 方案三：蓄水池方法 蓄水池方法用以解決n很大或者n實現不可知的情況。將k看成水池容量，n = length(S)看成一個事先未知的集合S的大小 ~~~ array R[k]; // result integer i, j; // fill the reservoir array for each i in 1 to k do R[i] := S[i] done; // replace elements with gradually decreasing probability for each i in k+1 to length(S) do j := random(1, i); // important: inclusive range if j <= k then R[j] := S[i] fi done ~~~ 個人的理解是，若文檔非空(至少有一行)，則先記下該行，然后看文檔是否讀完，若沒有(對應著 while more input lines)，當前行是第k行，則以1/k的概率(相當于把1到k行放在一起，等概率選擇)決定是否用第k行替換上次的選擇的結果。一次類推，最終array R[1] 中存儲的一個[0, n)的隨機