产生不重复的随机数
最后更新于：2022-04-01 21:40:22
我们在前几节，介绍了一篇三种方案解决**如何生成位于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)的随机
';