Chapter-Twelve.md

第十二章 取样问题

1. C 库函数 rand() 通常返回约 15 个随机位。使用该函数实现函数 bigrand() 和 randint(l, u)，要求前者至少返回 30 个随机位，后者返回[l,u] 范围内的一个随机整数。

下面两个函数分别返回一个较大的随机数（通常 30 位）和指定范围内的一个随机数：

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

2. 12.1 节要求所有的 m 元子集被选中的概率相等，这个条件比按等概率 m/n 选择每个整数更强。给出这样一个算法，其中每个元素的选中概率相等，但某些子集的选中概率比其他子集大一些。

为了从 0~n-1 范围内选择 m 个整数，可以先在该范围内随机选择一个数 i，然后输出 i，i+1,...,i+m+1(有可能绕回到 0)。这一方法选中每个整数的概率都是 m/n，但特定子集的选中概率明显偏大。

3. 证明当 m < n/2 时，基于集合的算法在找到一个不在集合中的数之前，所进行的成员测试的期望次数小于 2。

如果已被选中的整数少于 n/2 个，那么对一个已被随机选中的整数来说，其不被再次选中的概率大于 1/2。由于我们平均必须抛两次硬币才能得到正面，因此获得未被选中的整数的平均抽签次数小于 2。

4. 在基于集合的程序中对成员测试进行计数会产生组合数学和概率论中的许多有趣问题。程序平均需要进行多少次成员测试（用 m 和 n 的函数表示）？当 m=n 时需要进行多少次测试？什么情况下测试次数可能超过 m？

向统计学家请教“赠券收集问题”和“生日悖论”。

我们将集合 S 视为 n 个初始为空的坛子的集合。每调用一次 randint，我们就选中一个坛子往里面扔一个球；如果该坛子中已经有球了，则成员测试为真。需要多少个球来确保每个坛子中至少有一个球，这是统计学上著名的“赠券收集问题”（我必须收集多少张棒球卡才能确保拥有所有的 n？），答案大概为 nlnn。如果每个球都进入了不同的坛子，算法需要 m 次测试；而判断何时可能会有两个球进入同一个坛子，可以用“生日悖论”（如果一群人的人数达到 23 或更多，则很可能有两个人的生日是同一天）。一般说来，如果有 O(√n) 个球，则很可能会有两个球共享 n 个坛子中的某一个。

5. 本章描述了一个问题的集中算法，在本书网站上可以下载。在你的系统上度量它们的性能，并指出它们各自在什么情况下适用（表示为运行时间、空间等的约束函数）。

6. 【课堂练习】我在本科生算法课程中两次让学生生成有序子集。在学习排序和搜索之前，要求学生以 m=20 和 n=400 编写程序，主要评分标准是简短、清晰——运行时间不是问题。学习了排序和搜索之后，要求学生再次以 m=5 000 000 和 n=1 000 000 000 解决该问题，评分标准主要基于运行时间。

7. [V.A.Vyssotsky]生成组合对象的算法通常用递归函数来表达。Knuth 的算法如下所示：

void randselect(m, n)
        pre 0 <= m <= n
        post m distinct integers from 0..n-1 are
            printed in decreasing order
        if m > 0
            if (bigrand() % n) < m
                print n-1
                randselect(m-1, n-1)
            else
                randselect(m, n-1)

该程序按降序输出随机函数，如何使其按升序输出整数？请论证你的升序程序的正确性。如何使用该程序的基本递归结构生成 0~n-1 的所有 m 元子集？

为了使升序输出，可以把 print 语句放到递归调用之后。

8. 如何从 0~n-1 中随机选择 m 个整数，使得最终的输出顺序是随机的？如果有序列表中允许有重复整数，如何生成该列表？如果既允许重复，又要求按随机顺序输出，情况又如何？

为了按随机顺序输出不同的整数，在第一次生成每个整数时就将其输出，另见 答案 1.4。为了按序输出重复的整数，删除判断整数是否已在集合中的测试。为了按随机顺序输出重复的整数，使用下面的程序：

for i = [0, m)
    print bigrand() % n

9. [R.W.Floyd]当 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 用不同的集合接口实现这一算法。Floyd 的算法最早出现于 1986 年 8 月《ACM 通讯》的"编程珠玑"专栏，随后在我 1988 年的《编程珠玑 II》一书的第 13 章再次出现，以上两处都提供了对其正确性的简单证明。

10. 如何从 n 个对象（可以依次看到这 n 个对象，但事先不知道 n 的值）中随机选择一个？具体来说，如何在事先不知道文本文件行数的情况下读取该文件，从中随机选择并输出一行？

我们总选择第 1 行，并以概率 1/2 选择第 2 行，以概率 1/3 选择第 3 行，依此类推。在这一过程结束时，每一行的选中概率是相等的（都是 1/n，其中 n 是文件的总行数）：

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

11. [M.I.Shamos]在一种彩票游戏中，每位玩家有一张包含 16 个覆盖点的纸牌，覆盖点下面隐藏着 1~16 的随机排列，玩家刮开覆盖点则现出下面的整数。只要整数 3 出现，则判玩家负；否则，如果 1 和 2 都出现（顺序不限），则玩家胜。随机选择覆盖点的顺序就能够获胜的概率如何计算？请列出详细步骤，假定你最多可以使用一个小时的 CPU 时间。

该问题陈述表明，你可以使用计算机，但并非必须使用计算机。

我在“应用算法设计”课程的家庭作业中布置过完全一样的题目。如果学生给出了只需要几分钟的 CPU 时间就能计算出答案的方法，我会给他们零分；如果答案是“我需要和统计学教授讨论”，可以得到一半的分数；最佳答案应该像这样：

数字 4~16 对游戏没有影响，可以忽略。如果 1 和 2 都出现（顺序不限）在 3 之前，则玩家获胜。这种情况发生在 3 最后选中时，概率为 1/3。因此，随机选择覆盖点的顺序就能够获胜的概率精确地等于 1/3。

不要受问题陈述的误导，我们没必要仅仅因为可以使用 CPU 时间而去使用 CPU 时间。

12. 我为本章中某个程序编写的最初版本有一个严重的问题：m=0 时程序会死掉；m 取其他值时程序会生成看似随机的输出，但实际上并非如此。如何测试一个生成样本的程序，以确保其输出确实是随机的？

5.9 节介绍了 Kernighan 和 Pike 的 Practice of Programming。该书的 6.8 节描述了他们如何测试概率程序（我们在 15.3 节将看到另一个完成同一任务的程序）。