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

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

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

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

Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 711

Author 回答者: AaronKwong929

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

Author 回答者: Camliar

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

	1	2	3	4	5
0	0	0	0	0	0
1	1	2	3	4	5
2	2	4	6	8	10
3	3	6	9	12	15
4	4	8	12	16	20
5	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 的调用，具体操作可看到官方题解

Author 回答者: heretic-G

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

Author 回答者: 3N26

function rand5() {
  return (Math.random() * 6) | 0;
}
 
function rand7() {
  return (rand5() & 1) * 4 + (rand5() & 1) * 2 + (rand5() & 1);
}

Author 回答者: JLUssh

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

【Q689】JS 中如何原生实现 instanceOf 【Q691】如何实现一个 ORM 类似的 find 链式调用