本章的关注点是随机对象的选取。具体来讲，就是从n个对象中随机选取m个对象的问题，其中要用到随机数生成函数。
　　假设：一个能返回很大随机整数的的函数bigrand()，一个能返回i..j范围内均匀选择的随机整数函数randint(i,j)。
　　在C语言中，随机函数rand()通常返回约15个随机位，可以使用该函数实现上述bigrand()和randint()函数。

　　int bigrand(){
　　    return RAND_MAX*rand() + rand();
　　}
　　int randint(int l, int u){
　　    return l + bigrand() % (u-l+1);
　　}

Knuth的方法
　　Knuth的思想是从起始数字开始依次测试每个数字，根据已经选取的数目和剩下的数目来决定选取当前数字的概率。也就是说，如果要从r个剩余的整数中选出s个，我们以概率s/r选择下一个数。这样获得的随机序列从小到大依次排列而没有重复。伪代码：

　　select = m
　　remaining = n
　　for i = [0, n)
　　    if (bigrand() % remaining) < select
　　        print i
　　        select --
　　    remaining --

　　C++实现：

　　void genknuth(int m, int n){
　　    for (int i = 0; i < n; i++)
　　        /* select m of remaining n-i */
　　        if ( (bigrand() % (n-i)) < m ){
　　            cout << i << “\n”;
　　            m--;
　　        }
　　}

使用集合的方法
　　在一个初始为空的集合里插入随机整数，直到个数足够。伪代码：

　　initialize set s to empty
　　size = 0
　　while size < m do
　　    t = bigrand() % n
　　    if t is not in s
　　        insert t into s
　　        size ++
　　print the elements of s in sorted order

　　借助于C++标准模版库，用set表示集合可以很容易地实现上述代码：

　　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 << “\n”;
　　}

　　C++标准模版库规范每次插入操作都在O(log m)时间内完成，而遍历集合则需要O(m)时间，因此完整的程序需要O(mlogm)时间（当m相对于n比较小时）。

打乱数组顺序的方法
　　简单来说，就是把包含整数0~n-1的数组顺序打乱，然后把前m个元素排序输出。实际上该过程可以进一步简化——只打乱数组的前m个元素即可。

　　for i = [0, n)
　　    swap(i, randint(i, n-1))

　　C++代码如下：

　　void genshuf(int m, int n){
　　    int i, j;
　　    int *x = new int[n];
　　    for (i = 0; i < n; i++)
　　        x[i] = i;
　　    for (i = 0; i < m; i++){
　　        j = randint(i, n-1);
　　        int t = x[i]; x[i] = x[j]; x[j] = t;
　　    }
　　    sort(x, x+m);
　　    for (i = 0; i < m; i++)
　　        cout << x[i] << “\n”;
　　}

　　算法需要n个元素的内存空间和O(n+mlogm)的时间。

　　上述几种解决方法并没有覆盖所有情况。比如，当n为100万而m为n-10时，我们可能需要生成一个包含10个元素的有序随机样本，然后输出不在样本中的整数。再如，当m为1000万而n为231时，我们可能会先生成1100万个整数，然后排序并对其扫描以删除重复的元素，最后得到一个有1000万元素的有序样本。

原理总结

　　正确理解所遇到的问题。
　　提炼出抽象问题。 简洁、明确的问题陈述不仅可以帮助我们解决当前遇到的问题，还有助于我们把解决方案应用到其他问题中。
　　考虑尽可能多的解法。 很多程序员很快就发现了问题的“解决方案”，他们只愿花1分钟的时间思考，然后花一天的时间来写代码，而不是先花一个小时思考，再用一个小时来写代码。对文献的熟悉程度在这一阶段非常重要。
　　实现一种解决方案。 如果运气好的话，在前一阶段我们就能发现某种解决方案显著优于其他方案；否则我们就得列出几种性能比较好的方案，然后从中选择最佳的。我们应该用简单的代码和最有效的操作来实现最终选择的解决方案。
　　回顾。 改进的余地总是存在的。经过充分的研究和思考，任何解决方案都可能被改进；任何情况下，对于解决方案的理解一定能被改进。

习题部分

　　（习题9）当m接近于n时，基于集合的算法生成的很多随机数都要丢掉，因为他们之前已经存在于集合中了。能否给出一个算法，使得即使在最坏情况下也只使用m个随机数？
　　Bob Floyd在研究基于集合的算法时发现，该算法会丢掉其生成的一些随机数。因此他提出了另一个基于集合的算法，用C++实现如下：

　　void genfloyd(int m, int n){
　　    set<int> S;
　　    set<int>::iterator i;
　　    for (int j = n-m; j < n; j++){
　　        int t = bigrand() % (j+1);
　　        if (S.find(t) == S.end())
　　            S.insert(t); //t not in S
　　        else
　　            S.insert(j); //t in S
　　    }
　　    for (i = S.begin(); i != S.end(); i++)
　　        cout << *i << “\n”;
　　}

　　这个算法可被证明是正确的，在习题13.1和《编程珠玑II》的13章都有重新提到，并有正确性的简单证明。

　　（习题10）如何从n个对象（可以依次看到这n个对象，但事先不知道n的值）中随机选择一个？
　　在“算法设计与分析”课的Las Vegas算法部分的8皇后问题中曾用到过这种方法。具体来说，我们总选择第1个，并以1/2的概率选择第2个，以1/3的概论选择第3行，以此类推。

　　i = 0
　　while more input lines
　　    with probability 1.0/++i
　　        choice = this input line
　　print choice