程序的输入包含两个整数 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
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 的概率是 ,下面需要证明前 i 个元素出现在前 m 个数中的概率同样也是

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

得证

习题

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 元子集被选中的概率相等,这个条件比按等概率 选择每个整数更强。给出这样一个算法,其中每个元素的选中概率相等,但某些子集的选中概率比其他子集大一些。

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

3. 证明当 时,基于集合的算法在找到一个不在集合中的数之前,所进行的成员测试的期望次数小于 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 中每一个被抽中的概率是 。对于前 n-1 个元素来说,它被抽中的概率为:

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

其中 代表随机数就是 m-1 个中的其中之一,代表选中的数不是 m-1 中的一个。 对于第 n 个元素来说:

其中 代表随机数就是 n代表随机数是 m-1 中的一个,也会把 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 的值)中随机选择一个?具体来说,如何在事先不知道文本文件行数的情况下读取该文件,从中随机选择并输出一行?

蓄水池算法。我们总是选择第一个对象,以 的概率选择第二个,以 的概率选择第三个,以此类推,以 的概率选择第 m 个对象。当该过程结束时,每一个对象具有相同的选中概率,即,证明如下: 第 m 个对象最终被选中的概率 P = 选择 m 的概率 × 其后面所有对象不被选择的概率,即:

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

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