【Q690】如何根据 random5 随机生成 [0, 5]，生成一个函数 random7？

[shfshanyue]

已知有一个函数 叫做 random5，执行这个函数会随机返回 0-5 之间任意一个数，概率相同。

根据这个 random5，实现一个 random7，要求执行这个函数后随机返回 0-7 之间任意一个数，概率相同。

这是一道群友分享的百度面经中的问题。

[AaronKwong929]

https://www.growingwiththeweb.com/2014/03/given-random5-implement-random7.html 看到一题近似的，不过random5和random7 是返回[0, 5]和[0, 7]

[Camliar]

• 参考 leetcode 470. 用 Rand7() 实现 Rand10()-
• 方法：拒绝采样
• 思路：random5生成 [0, 5]每个数的概率是 $ \frac {1}{6} $， 使用两次 random 函数，相乘，找到等概率出现的 8个数就可以，不满足的数据排除掉

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	1	2	3	4	5
2	0	2	4	6	8	10
3	0	3	6	9	12	15
4	0	4	8	12	16	20
5	0	5	10	15	20	25

	0	1	2	3	4	5
P	$\frac{11}{36}$	$\frac{1}{36}$	$\frac{2}{36}$	$\frac{2}{36}$	$\frac{3}{36}$	$\frac{2}{36}$
	6	8	9	10	12	15
P	$\frac{2}{36}$	$\frac{2}{36}$	$\frac{1}{36}$	$\frac{2}{36}$	$\frac{2}{36}$	$\frac{2}{36}$
	16	20	25
P	$\frac{1}{36}$	$\frac{2}{36}$	$\frac{1}{36}$

根据上图可知，我们只需要取 [1, 2, 3, 5, 6, 8, 9, 12, 15],这几个数，对8取余后可得到：

1	2	3	4	5	6	0	1	7
$\frac{1}{36}$	$\frac{2}{36}$	$\frac{3}{36}$	$\frac{2}{36}$	$\frac{2}{36}$	$\frac{2}{36}$	$\frac{2}{36}$	$\frac{1}{36}$	$\frac{2}{36}$

至此，我们可以得到等概率的[0, 7] 之间的数，每个数出现的概率为 $\frac{2}{36}$

故，简单粗暴的方式可用以下方式实现：

    def random5(self):
        return randint(0, 5)
    
    def random7(self):
        picked = [1, 2, 3, 5, 6, 8, 9, 12, 15]
        while True:
            rd1 = self.random5()
            rd2 = self.random5()
            if (rd1 * rd2) in picked:
                return (rd1 * rd2) % 8
            rd1 = self.random5()
            rd2 = self.random5()

如果要更进一步优化，减少random5 函数的调用，我们就需要优化，如果随机出现的值不在我们采样的范围中时，怎么去减少对函数 random5 的调用，具体操作可看到官方题解

[heretic-G]

function rand5 () {
    return Math.random() * 6 | 0
}

function rand7 () {
    while (true) {
        let num = rand5() * 6 + rand5()
        if (num < 32) {
            return num % 8
        }
    } 
};

[3N26]

function rand5 () {
    return Math.random() * 6 | 0
}

function rand7 () {
    return (rand5() & 1) * 4 + (rand5() & 1) * 2 + (rand5() & 1);
};

[JLUssh]

直接进行缩放是不是就行了？ [0, 5] * 1.4 rand7 = rand5() * 1.4