每日算法系列【LeetCode 470】用 Rand7() 实现 Rand10()

算法 leetcode

编程算法

发布日期: 2020-01-18

作者: 韦阳

文章字数: 1.2k

阅读时长: 4 分

阅读次数:

关注公众号【算法码上来】，每日算法干货马上就来！

题目描述

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

思考

rand7()调用次数的期望值是多少 ?
你能否尽量少调用 rand7() ?

题解

刚看到这题觉得挺有意思的，再看一脸懵逼，这怎么做？后来看了题解才懂了，原来是这个意思。

题目要求只能给你用 rand7 函数，也就是均匀生成 1 到 7 之间的整数。但是现在要求你生成 1 到 10 之间的整数，那么肯定只生成一次是不够的，因为状态数都不够嘛，那就生成多次看看。

如果生成两次，那么就得到了两个 1 到 7 之间的整数，然后怎么转换为 1 到 10 呢。如果这两个数两两组合，那么可以得到 49 种状态，可以用来表示 1 到 49 这 49 个数字，如果想要让 1 到 10 均匀分布，那么每个数字最多只能分配 4 次。具体分配情况如下所示：

1  2  3  4  5  6  7
8  9  10 1  2  3  4
5  6  7  8  9  10 1
2  3  4  5  6  7  8
9  10 1  2  3  4  5
6  7  8  9  10 .  .
.  .  .  .  .  .  .

注意：每行下标代表第一个随机数 1 到 7 （r1 表示），每列下标代表第二个随机数 1 到 7 （r2 表示）。而转换后的随机数可以表示为 $(7 (r1 - 1) + r2 - 1) % 10 + 1$ ，注意到最后 9 个数没有用到，因为它们不足以表示 1 到 10 这 10 个数，如果表示了概率就不等了。

那么如果根据上面式子算出来落在了最后 9 个数范围内怎么办呢？这时候我们就拒绝它，重新生成两个数就行了，直到落在前 40 个数范围里。这种方法的期望采样次数是多少呢？
$$
\begin{aligned}
E &= 2 + 2 \cdot \frac{9}{49} + 2 \cdot (\frac{9}{49})^2 + \cdots \
&= 2 \sum_{n=0}^{\infty}{(\frac{9}{49})^n} \
&= 2 \cdot \frac{1}{1-\frac{9}{49}} \
&=2.45
\end{aligned}
$$

所以平均只需要 2.45 次就可以均匀的采样到 1 到 10 之间的整数啦。那么这背后的数学原理是什么呢？其实就是拒绝采样。

蒙特卡洛方法大家应该都很熟悉了，就是采样来求分布，比如求一个直径为 1 的圆的概率，我们可以用一个边长为 1 的正方形包住它，然后随机往里面扔豆子，扔 10000 个，看最后有多少落在了圆里面，那么除以 10000 就是圆的面积了。

而拒绝采样跟这类似，就是一个分布 $p(x)$ 形式比较复杂，累积分布函数不好求，所以不好采样。那么我们可以用一个标准分布 $q(x)$ 来近似它，并且用系数 $k$ 来控制 $q(x)$ 的大小，使得 $k \cdot q(x) \ge p(x)$ ，这就类似于上面的用正方形包住了圆形嘛。然后 $q(x)$ 是好采样的嘛，所以根据 $q(x)$ 采样出一个 $x’$ ，然后再在 0 到 $k \cdot q(x’)$ 之间采样一个数 $t$，如果 $t$ 落在了 0 到 $p(x’)$ 之间，那就接受这个采样，否则就拒绝它，重新采样。这种方法采出来的 $x’$ 是服从分布 $p(x)$ 的，因为你采样得到 $x’$ 的概率是 $q(x’)$ ，而接受的概率是 $\frac{p(x’)}{k \cdot q(x’)}$ ，所以最终接受 $x’$ 的概率就是 $\frac{p(x’)}{k}$ 。因此 $k$ 要设置的尽量小，这样接受的概率才大，期望的采样次数才少。但是又不能设置太小，因为要满足 $k \cdot q(x) \ge p(x)$ 的前提条件才行。

代码

c++

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int r1, r2, num;
        do {
            r1 = rand7();
            r2 = rand7();
            num = (r1 - 1) * 7 + r2;
        } while (num > 40);
        return (num - 1) % 10 + 1;
    }
};