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

题目描述

已有方法 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 表示）。而转换后的随机数可以表示为 ，注意到最后 9 个数没有用到，因为它们不足以表示 1 到 10 这 10 个数，如果表示了概率就不等了。

那么如果根据上面式子算出来落在了最后 9 个数范围内怎么办呢？这时候我们就拒绝它，重新生成两个数就行了，直到落在前 40 个数范围里。这种方法的期望采样次数是多少呢？

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

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

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

代码

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;
    }
};

      

后记

这题题目虽简单，背后的思想还是很有意思的，拒绝采样可以用在深度学习中的很多应用场景里，特别是你的分布很难进行采样的时候，就可以用拒绝采样来模拟。

当然这题还有其他采样方法可以缩小期望采样次数，比如如何利用这 9 个被拒绝的点呢？留给大家思考（其实是我懒得写了）。