LeetCode 470. 用 Rand7() 实现 Rand10()（中）

如何进行概率拼凑以及概率转换？

Question

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。不要使用系统的 Math.random() 方法。

示例 1: 

1
2
输入: 1
输出: [7]
示例 2: 
1
2
输入: 2
输出: [8,4]
示例 3: 
1
2
输入: 3
输出: [8,1,10]
提示: rand7 已定义。 传入参数: n 表示 rand10 的调用次数。

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

Intuition

题目无非就是凑出1/10的概率出来，而现在我们只有1/7的概率，可以利用乘法原则1/10=1/5 * 1/2。 因为是随机的，所以每一次的选择都不会影响下一次的概率分布，所以代码中凑出1/5和1/2的方式是可行的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:

    def rand10(self):
        """
        :rtype: int
        """
        first = 7
        second = 4
        # first不会大于5，范围在0-4之间。
        while first > 5:
            first = rand7()
        # 至此，first的概率是1/5的概率（0、1、2、3、5）。
        
        # second在0-3、5-6之间。
        while second == 4:
            second = rand7()
        # 当随机出来的second在5-6之间时，统一设置为5。当second在0-3之间时，统一设置为0。
        second = 5 if second > 4 else 0
        # 至此，second的概率是1/2（0、5）
       
        # 最终，输出的随机数的生成概率为 1/10 = 1/5 * 1/2。
        return first + second

Extension

已有概率函数 Rand5() 能够产生0-4的随机整数，如何获得 Rand7() 生成0-6的随机整数 ？

rand5可以随机生成1,2,3,4,5；rand7可以随机生成1,2,3,4,5,6,7。 rand5并不能直接产生6，7，所以直接用rand5去实现函数rand7似乎不太好入手。 如果反过来呢？给你rand7，让你实现rand5，这个好实现吗？

通用概念

一个非常直观的想法就是不断地调用rand7，直到它产生1到5之间的数，然后返回。 代码如下：

1
2
3
4
5
def rand5():
    x = 2 ** 31
    while x > 5:
        x = rand7()
    return x

那么这个 rand5 的生成概率是1到5呢？上面的函数中有个while循环，只要没生成1到5间的数就会一直执行下去。 因此，我们要的1可能是第一次调用Rand7时产生，也可能是第二次，第三次，…第n次。 第1次就生成1，概率是1/7；第2次生成1，说明第1次没生成1到5间的数而生成了6，7， 所以概率是(2/7)*(1/7)，依次类推。生成1的概率计算如下：

1
2
P(x=1)=1/7 + (2/7) * 1/7 + (2/7)^2 * 1/7 + (2/7)^3 * 1/7 + ... + (2/7)^n * 1/7
      =1/7 * (1 + 2/7 + (2/7)^2 + ... + (2/7)^n) // 等比数列

\(1 + \frac{2}{7} + (\frac{2}{7})^2 + ... + (\frac{2}{7})^n\) 是一个 \(a_1=1\)，\(q=\frac{2}{7}\) 的等比数列。等比数列前 \(n\) 项计算公式如下： \[ S_n = \frac{a_1 \times (1-q^n)}{1-q} (q \neq 1) \] 所以： \[ 1 + \frac{2}{7} + (\frac{2}{7})^2 + ... + (\frac{2}{7})^n = \frac{1 \times (1-\frac{2}{7}^n)}{1-\frac{2}{7}} = \frac{1}{\frac{5}{7}} =\frac{7}{5} \] 因此：

1
2
3
P(x=1)=1/7 * 1 / (1 - 2/7)
      =1/7 * 7/5
      =1/5

上述计算说明Rand5是等概率地生成1,2,3,4,5的(1/5的概率)。从上面的分析中， 我们可以得到一个一般的结论，如果 M > N，那么一定可以用 Rand_M去实现 Rand_N。其中， Rand_M表示等概率生成1到M的函数，Rand_N表示等概率生成1到N的函数。代码如下：

1
2
3
4
5
def rand_N():
	x = 2 **31
	while x > N:
		x = rand_M()
	return x

从 Rnad5 到 Rand7

回到正题，现在题目要求我们要用Rand5来实现Rand7，只要我们将Rand5 映射到一个能产生更大随机数的Rand_A，其中A > 7，就可以套用上面的模板，实现由Rnad5 到 Rnad_A，再到Rand7了。 这里要注意一点的是，你映射后的Randa一定是要满足等概率生成1到a的。比如，5 * (Rand5() - 1) + Rand5()，Rand5产生1到5的数，减1就产生0到4的数，乘以5后可以产生的数是：0,5,10,15,20。 再加上第二个Rand5()产生的1,2,3,4,5。我们可以得到1到25， 而且每个数都只由一种组合得到，即上述代码可以等概率地生成1到25。且概率为 1/25。

套用上面的模板，我们可以得到如下代码：

1
2
3
4
5
6
7
8
def rand25():
    return 5 * (rand5() - 1) + rand5()

def rand7():
    x = 2**32
    while x > 7:
        x = rand25()  # 想到这个很重要
    return x

上面的代码有什么问题呢？可能while循环要进行很多次才能返回。 因为Rand25会产生1到25的数，而只有1到7时才跳出while循环， 生成大部分的数都舍弃掉了。这样的实现明显不好。我们应该让舍弃的数尽量少， 于是我们可以修改while中的判断条件，让x与最接近25且小于25的7的倍数相比。 于是判断条件可改为x > 21，于是x的取值就是1到21。 我们再通过取模运算把它映射到1-7即可。代码如下： 

1
2
3
4
5
6
7
8
def rand25():
    return 5 * (rand5() - 1) + rand5()

def rand7():
    x = 2**32
    while x > 21:
        x = rand25()  # 想到这个很重要
    return x % 7 + 1

参考链接

使用rand5()生成rand7()

Summary

从 Rand_m 到 Rand_n ：

  • 如果 m > n（从大到小），套用模板，直接解决问题。

    1
    2
    3
    4
    5
    def rand_N():
    	x = 2 **31
    	while x > N:  # 根据实际情况，这个条件还可以优化。
    		x = rand_M()
    	return x

  • 如果 m < n（从小到大），用 Rand_m 构造 Rand_x = m * (rand_m() – 1) + Rand_m()，如果 x < n，那就再次构造 Randa_x = a * ( Rand_x – 1) + Rand_x，直到 x > n。然后，再套用模板，直接解决问题。

    1
    2
    3
    4
    5
    6
    7
    8
    def rand_x:
    	return m * (rand_m() – 1) + Rand_m()  # 可以多次重复，直到x>n。

    def rand_N():
    	x = 2 **31
    	while x > N:  # 根据实际情况，这个条件还可以优化。
    		x = rand_x()
    	return x