我们在前几节，介绍了一篇三种方案解决**如何生成位于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)的随机