## 取样问题
本章讲述了一个小的随机抽样问题，并用不同的方法来解决它。
问题：对于整数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》
