470. 用 Rand7() 实现 Rand10()

Difficulty
Medium
Tags
随机算法
URL
https://leetcode-cn.com/problems/implement-rand10-using-rand7/
Star
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
示例 1:
输入:1
输出:[2]
示例 2:
输入:2
输出:[2,8]
示例 3:
输入:3
输出:[3,8,10]
提示:
  • 1 <= n <= 105
进阶:
  • 你能否尽量少调用 rand7() ?

法 1 万能套路：通过二进制构造

思路
  • 先用给定的API生成 一个 0，1 等概率的生成器
  • 然后再用这个等概率的 0，1生成器来构造二进制下的 n
二进制的每一位出现0和1的可能性都是相同的，所以能生成的每一个数概率都是相同的。
【步骤】
  1. 下面将需要生成的随机数中最大值记为n
  1. 先去生成一个等概率产生0和1的方法：rand2() 。
      • 不要去纠结为什么返回值不是1和2，因为方便二进制位运算。
      • 实现：调用 rand7() ，1,2,3 返回1，4,5,6 返回2，7 重来。
  1. 将n转为二进制，看看是几位的二进制。
      • 例如本题的 10 ，二进制为 1010 。也就是说仅仅需要4位二进制数就能表示10进制的10。 用这个 rand2() 方法生成n的每个二进制位。
  1. 创建一个数为 rand2() ，每次左移一位再加 rand2() 。
  1. 如果出现不符合题意的情况，再次调用 rand10() 。
      • 例如如上步骤可能生成 0000 , 1011 、…… 、1111 （分别为0,11、 …… 、15），显然这些都是不在[1,10]中的正整数，所以只能重新生成。
       
题解
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        res = 0
        # 此处左移动 4 次， 因为 10 最少需要用 4 个二进制位表示
        for i in range(0, 4):
            temp = self.rand2()
            res = (res << 1) ^ temp
        
				# 满足条件就返回
        if 0 < res <= 10:
            return res
        return self.rand10()

    def rand2(self):
        # 等概率的 0 1 生成器

        # 先产生一个 [0,6] 的随机数
        res = rand7()
        while res == 7:
            res = rand7()

        return res % 2
另外一种写法
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        val = 0
        for i in range(0, 4):
            val |= self.rand01() << i

        while val > 9:
            val = 0
            for i in range(0, 4):
                val |= self.rand01() << i
        return val + 1
        
        
    def rand01(self):
        val = rand7()
        while val == 7:
            val = rand7()
        return val % 2

法 2 独立随机事件+古典概型

思路
rand7() 构造 rand10()
  1. 构造 2 次采样，分别有 2 和 5 种结果，组合起来便有 10 种概率相同的结果。
  1. 把这 10 种结果映射到 [1,10] 即可。
第一步具体要如何构造采样是自由的，比如 rand7() 拒绝 7，然后对 [1,6]采样，把奇数和偶数作为 2 种结果，这 2 种结果的概率均为 0.5 。rand7()拒绝 6,7，然后对 [1,5] 采样，有 5 种结果，每种概率均为 0.2 。
rand7() 构造任意范围的随机数发生器
上述方法理论上可以构造任何范围的随机数发生器，比如 rand11()rand11() ：
  1. 构造 2 次采样，分别有 2 和 6种结果，组合起来便有 12 种概率相同的结果。
  1. 把这 12 种结果映射到 [1,12]，然后再拒绝 12 即可。
rand100() ：
构造 33 次采样，分别有 4,5,5种结果，组合起来便有 100种概率相同的结果。 把这 100 种结果映射到 [1,100] 即可。

法 3 万能套路：通过扩大概率区间

思路
rand0toN-->rand0toM 1. 首先 rand0toN-->rand0toX ，其中 X>=M，且X是N整数倍。实现方式如下：
def rand0toX():
		# 只能是这样写，不然就不是等概率的，且不能化简
		return rand0toN() * (N+1) + rand0toN()
  1. 然后 rand0toX-->rand0toY, Y是(M+1)的整数倍-1，这一步可以通过拒绝采样得到。
  1. 最后 rand0toY() % (M+1) 即 得到了 [0,M]的随机数。
本题，先生成 [0,39]之间的随机数 val，然后val % 10 得到 [0, 9]之间的随机数。
为什么是生成[0,39]的随机数呢？
因为已有的是[0,6]的随机数，对[0,6]的随机数 通过 rand0to6() * 7 + rand0to6() 先得到了[0, 48]之间的随机数。然后拒绝采样得到 [0, 39]的随机数。
当然，通过拒绝采样得到 [0, 19] or [0, 29] 的随机数都是可以的。但是这样拒绝的次数有点多，时间消耗较大。
题解
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        return self.rand39() % (9+1) + 1
 
    def rand39(self):
        val = (rand7()-1) * 7 + (rand7()-1)
        while val >= 40:
            val = (rand7()-1) * 7 + (rand7()-1)

        return val