《编程珠玑》第 12 章──抽样

程序的输入包含两个整数 mn,其中 m<n 。输出是 0~n-1 范围内 m 个随机整数的有序列表,不允许重复。从概率的角度说,我们希望得到没有重复的有序选择,其中每个选择出现的概率相等。

解决方案

第一种方案

Knuth algorithm S

1
2
3
4
5
6
7
8
void getknuth(int m, int n) {
for (int i = 0; i < n; ++i) {
if ((rand() % (n - i)) < m) {
printf("%d\n", i);
--m;
}
}
}

第二种方案

使用集合

1
2
3
4
5
6
7
8
9
10
11

void gensets(int m, int n) {
set<int> S;
while (S.size() < m) {
S.insert((int) random() % n);
}
set<int>::iterator i;
for (i = S.begin(); i != S.end(); ++i) {
cout << *i << endl;
}
}

第三种方案

0~n-1 的数组顺序打乱,然后取前 m 个元素即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void genshuf(int m, int n) {
int i, j;
auto *x = new int[n];
for (i = 0; i < n; ++i) {
x[i] = i;
}
for (i = 0; i < m; ++i) {
j = rand() % (n - 1 - i) + i + 1;
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
sort(x, x + m);
for (i = 0; i < m; ++i) {
cout << x[i] << endl;
}
}

第四种方案

补充一下蓄水池算法(Reservoir sampling),假设 n 非常大,不能一次性全部读入内存中。第三种方法洗牌算法(Fisher-Yates shuffle)把 n 个数字全部打乱了,而其实我们只需要前 m 个,所以没必要把后面的也打乱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void reservoir_sampling(int m, int n) {
auto *x = new int[n];
for (int i = 0; i < n; ++i) {
x[i] = i;
}
for (int i = m; i < n; ++i) {
int j = rand() % i;
if (j < m) {
int tmp = x[j];
x[j] = x[i];
x[i] = tmp;
}
}
for (int i = 0; i < m; ++i) {
cout << x[i] << endl;
}
}

证明:
采用数学归纳法。

现在我们对 i+1 这个数进行分析,程序中 i+1 这个元素被选中进入前 m 的概率是 $\frac{m}{i+1}$,下面需要证明前 i 个元素出现在前 m 个数中的概率同样也是 $\frac{m}{i+1}$。

  1. i = m+1 时,第 m+1 个元素被选中的概率是 $\frac{m}{m+1}$,此时前 m 出现概率是 $\frac{m}{m+1}$,结论成立。
  2. 假设 j = i 的时候结论成立,以 $\frac{m}{i}$ 的概率来选择第 i 个元素,前 i-1 个元素出现的概率都是 $\frac{k}{i}$。
  3. j = i+1 的时候,以 $\frac{k}{i+1}$ 得概率选择第 i+1 个元素。前 i 个元素出现的概率由两部分组成。
    • i+1 个元素没有被选择。
    • i+1 个元素被选择,但是没有替换前 m 个元素。
      首先第 i+1 个元素被选择的概率是 $\frac{m}{i+1}$,然后选择 m 个任意一个,被替换的概率是 $\frac{1}{m}$。所以前 i 个元素任意一个被替换的概率是 $\frac{m}{i+1}\times \frac{1}{m} = \frac{1}{i+1}$。没有被替换的概率是 $1-\frac{1}{i+1} = \frac{i}{i+1}$。所以前 i 个元素出现的概率是 $\frac{m}{i}\times \frac{i}{i+1} = \frac{m}{i+1}$

得证

习题

1

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

1
2
3
4
5
6
7
int bigrand() {
return RAND_MAX * rand() + rand();
}

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

2

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

先随机选择一个数 i,然后输出 ii+1,…,i+m-1。这样的话,每个数字被选中的概率是 $\frac{m}{n}$,但是连续的区间出现的概率肯定比随机分布的区间出现的概率大。

3

证明当 $m<\frac{n}{2}$ 时,基于集合的算法在找到一个不在集合中的数之前,所进行的成员测试的期望次数小于 2。

因为被选中的数字的总数小于 $\frac{n}{2}$,所以不被抽中的概率大于 0.5,那么因为期望要等于 1,所以次数要小于 2。

7

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

1
2
3
4
5
6
7
void randselect(m,n)
if m > 0
if (bigrand() % n) < m
print n-1
randselect(m-1,n-1)
else
randselect(m,n-1)

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

理解递归程序的栈,就可以很容易改成下面的了。

1
2
3
4
5
6
7
void randselect(m,n)
if m > 0
if (bigrand() % n) < m
randselect(m-1,n-1)
print n-1
else
randselect(m,n-1)

8

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

输出顺序是随机的

1
2
3
for i = [0, k)
swap(i, randint(i, n-1))
print x[i]

允许有重复数字

1
2
3
for i = [0, m)
x[i] = bigrand() %n
sort(x, x+i)

随机顺序输出重复数字

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

9

[R.W.Floyd] 当 m 接近于 n 时,基于集合的算法生成的很多随机数都要丢掉,因为它们之前已经存在于集合中了。能否给出一个算法,使得即使在最坏情况下也只使用 m 个随机数?

m 等于 1,结论显然成立。假设 m-1n-1 时结论成立,那么 n-1 中每一个被抽中的概率是 $\frac{m-1}{n-1}$。对于前 n-1 个元素来说,它被抽中的概率为:

总被选中的概率 P = 上一轮被选中的概率 + 上一轮未被选中的概率 * 本轮被选中的总概率

$$
P = \frac{m-1}{n-1} + \left(1 - \frac{m-1}{n-1}\right)\times \frac{1}{n} = \frac{m}{n}
$$

其中 $\frac{m-1}{n-1}$ 代表随机数就是 m-1 个中的其中之一,$\left(1 - \frac{m-1}{n-1}\right)\times \frac{1}{n}$ 代表选中的数不是 m-1 中的一个。
对于第 n 个元素来说:

$$
P = \frac{1}{n} + \frac{m-1}{n} = \frac{m}{n}
$$
其中 $\frac{1}{n}$ 代表随机数就是 n,$\frac{m-1}{n}$代表随机数是 m-1 中的一个,也会把 n 加入抽样中。

综上所有元素被抽中的概率都是$\frac{m}{n}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
} else {
S.insert(j);
}
}
for (auto &it:S) {
cout << it << endl;
}
}

10

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

蓄水池算法。我们总是选择第一个对象,以 $\frac{1}{2}$ 的概率选择第二个,以 $\frac{1}{3}$ 的概率选择第三个,以此类推,以 $\frac{1}{m}$ 的概率选择第 m 个对象。当该过程结束时,每一个对象具有相同的选中概率,即$\frac{1}{n}$,证明如下
第 m 个对象最终被选中的概率 P = 选择 m 的概率 * 其后面所有对象不被选择的概率,即
$$
P = \frac{1}{m}\times \left(\frac{m}{m+1} \times \frac{m+1}{m+2} \times \dots \times \frac{n-1}{m}\right) = \frac{1}{n}
$$

11

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

只需要考虑 1、2 和 3。那么 3 放到两者后面的概率是 $\frac{1}{3}$。