## 取樣問題
本章講述了一個小的隨機抽樣問題,并用不同的方法來解決它。
問題:對于整數m和n,其中m<n,輸出0~n-1范圍內m個隨機整數的`有序列表`, 不允許重復。
比如m=3, n=5,那么一種可能輸出是0,2,3(要求有序)。實現1來自Knuth的TAOCP, 時間復雜度O(n):
~~~
void GenKnuth(int m, int n) {
for(int i=0; i<n; ++i) {
if((bigrand()%(n-i)) < m) {
cout<<i<<endl;
--m;
}
}
}
~~~
其中,bigrand()的作用是返回一個很大的隨機整數。
實現2:在一個初始為空的集合里面插入隨機整數,直到個數足夠。代碼如下:
~~~
void GenSets(int m, int n) {
set<int> s;
while(s.size() < m)
s.insert(bigrand() % n);
set<int>::iterator i;
for(i=s.begin(); i!=s.end(); ++i)
cout<<*i<<endl;
}
~~~
實現3:把包含整數0~n-1的數組順序打亂,然后把前m個元素排序輸出。 該方法的性能通常不如Knuth的算法。代碼如下:
~~~
void GenShuf(int m, int n) {
int x[n];
for(int i=0; i<n; ++i)
x[i] = i;
for(int i=0; i<m; ++i) {
int j = randint(i, n-1);
swap(x[i], x[j]);
}
sort(x, x+m);
for(int i=0; i<m; ++i)
cout<<x[i]<<endl;
}
~~~
深入閱讀:Don Knuth的《The Art of Computer Programming, Volume 2: Seminumerical Algorithms》