rand(7)模拟rand(10)的背后

刷LeetCode遇到这样一道题：用 Rand7() 实现 Rand10()，本文以这题为引子，深入探讨一下其背后的一些知识。

题目描述如下：

• 给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

  你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

对于这题，有一种更加通用的问法：如何用rand(m)模拟rand(n)？对于这题，m=7，n=10。

这种类型的题还有很多，比如：“ 一个不均匀的硬币，怎么抛硬币可以让我们得到50% 50%的概率事件 ”。

这类问题的核心是**“拒绝采样”**。

所谓“拒绝采样”，我的理解就是，设计一种采样方式，我们取其中若干种可能作为结果集，当遇到其他情况时，本次操作作废，继续下一次采样。

这么说可能比较抽象，用上面抛硬币的例子来理解下，对于这个问题，我们可以这样考虑：

抛两次，先正后反记为1，先反后正记为2。 1和2就是等可能事件。 那么我们是如何避开硬币不均匀的事情的呢，本质就是我们拒绝了一部分事件，比如两次都是正面，或者都是反面，就作废，重新采样。

重新回到“用Rand7模拟Rand10模拟”，这个问题该如何解决呢？

回想抛硬币问题，我们的解决思路其实是：设计一种采样方式，构造两种等可能采样结果，拒绝其他所有类型采样结果，这样我们就得到两种概率各位50%的采样结果。

同样地，我们要模拟Rand10，需要设计一种采样方式，构造10种等可能结果，拒绝其他采样结果就可以了。

• 方案1： 一种非常巧妙的方式是，用Rand7进行两次采样，

  • 第一次采样，设计一个Rand2，决定数字是1~5还是6 ~10

    具体来说，拒绝7，接受1-6，奇数表示1~5，偶数表示6-10。这样我们得到了2种等概率事件。

  • 第二次采样，设计一个Rand5，拒绝6-7，接受1-5。这样我们得到了5种等概率事件。

  • 两次采样结果合到一起，就得到以10种等概率事件，结果用rand5() + rand2() * 5表示即可。

    class Solution extends SolBase {
        public int rand10() {
            //思路：使用ran7在【0，6】直接选一个数 使用ran7在【0，5】之间选一个数
            int a=rand7();int b=rand7();
            while(a==7) a=rand7();//a不能为7 必须为【1，6】这样才能保证奇偶都是1/2概率
            while(b>5) b=rand7();//b不能为5以上 因为一会可能要加5
            return ((a&1)==0?0:5)+b;//判断a奇偶性1/2 * b取值【1，5】之间1/5=1/10
        }
    }

• 方案2： 对于其他方案，本质和方案1是一样的，就是想办法利用Rand7进行多次采样，构建10种等概率事件即可。这里举个简单例子。我们可以用Rand7()进行两次采样，将两次采样结果相乘，可以得到如下结果：

  

• 一种可能的方案是，计算每个数的生成概率，我们从中挑选10个等概率的事件即可。

  

• 另一种更优的方案是，我们可以调用两次Rand7()，那么可以生成 [1, 49]之间的随机整数，我们只用到其中的前 40 个来实现Rand10()，而拒绝剩下的 9 个数，如下图所示（把两次采样结果相乘后，对10取余）。

  

  具体代码实现如下：

  class Solution extends SolBase {
        public int rand10() {
            int row, col, idx;
            do {
                row = rand7();
                col = rand7();
                idx = col + (row - 1) * 7;
            } while (idx > 40);
            return 1 + (idx - 1) % 10;
        }
    }

打赏