如何根据 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个数就可以，不满足的数据排除掉
| 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 的调用，具体操作可看到官方题解
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);
}