拒绝采样

拒绝采样就是，如果一个被采样本不满足你的需求，就放弃这个样本，重新再采一个
更一般地说，拒绝采样就是【每一次采样都存在一定概率会被舍弃并进行重新采样，从而使得采集的样本能够拟合目标概率分布】

拒绝采样，解决的问题是，通过对一个简单的概率密度分布进行选择性采样，完成对一个新的概率密度分布（往往是相对复杂的概率密度分布）的采样

一般而言，一个复杂的概率密度分布是不方便直接采样的，因为每一个样本对应的概率可能都非常杂乱无章；而在均匀分布、正态分布这些简单的概率密度分布下进行采样，则是比较容易实现的

那么，我们可以在对简单概率密度分布进行采样后，选择性地舍弃一些样本然后重新采样，从而模拟出在新的概率密度函数下的采样结果

leetcode 470. 用 Rand7() 实现 Rand10()

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：
这个题目的本质就是基于1/7的均匀分布，生成1/10的均匀分布

拆分后放大求解

放大求解

由1/7均匀分布变换到1/6的均匀分布很简单，只要采样得到7，就舍弃这个结果再采一次，这样我们就会得到等概率的1～6

因此，由1/7均匀分布到1/n（n < 7）均匀分布是很容易的

拆分

注意到1/10可以拆解成1/2 * 1/ 5，因此我们设置两次独立采样，分别服从1/2均匀分布和1/5均匀分布，将两次采样的结果视为一次事件，就可以达到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
        """
        # 1/2均匀采样
        a = rand7()
        while a == 7:
            a = rand7()
        num = 0 if a % 2 == 0 else 5

        # 1/5均匀采样
        b = rand7()
        while b > 5:
            b = rand7()
        return num + b

缩小再放大求解

核心公式
(rand(X)-1)*Y + randY() -----生成 [1,X*Y]区间，并且等概率

这样，通过(rand7()-1)*7 + rand7() 我们就可以从1-7的随机整数扩张到1-49的随机整数，即从1/7均匀分布缩小到1/49均匀分布，而从1/49均匀分布到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
        """
        temp = (rand7() - 1) * 7 + rand7()
        while True:
            if temp > 40 :
                temp = (rand7() - 1) * 7 + rand7()
            else:
                break
        return (temp - 1) // 4 + 1