用 Rand7() 实现 Rand10()

## 1 题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

**示例 1:**

```txt
输入: 1
输出: [7]
```

**示例 2:**

```txt
输入: 2
输出: [8,4]
```

**示例 3:**

```txt
输入: 3
输出: [8,1,10]
```

**提示:**

1. rand7 已定义。
2. 传入参数: n 表示 rand10 的调用次数。

**进阶:**

1. rand7()调用次数的 期望值 是多少 ?
2. 你能否尽量少调用 rand7() ?

## 2 问题分析

1. 首先需要知道：
   1. **在输出域上进行定量整体偏移**，**仍然满足等概率**，即要实现 0~6 随机器，只需要在 $rand7()$ 的返回值上进行-1 操作即可。
   2. **输出域的拼接/叠加不满足等概率**，例如 $rand7() + rand7()$ 会产生 $[2, 14]$ 范围内的数，但每个数并非等概率：
      1. 产生 2 的概率为：有 1 种情况，即 $(1, 1)$，其概率为 $\frac17 \times \frac17 = \frac1{49}$。
      2. 产生 4 的概率为：有三种情况，分别为 $(1, 3)$、$(2, 2)$、$(3, 1)$，其概率为 $\frac17 \times \frac17 + \frac17 \times \frac17 + \frac17 \times \frac17 = \frac3{49}$。
   3. 上述做法出现概率分布不均的情况，是因为**两次随机值的不同组合「相加」会出现相同的结果**（$(1, 3)$、$(2, 2)$、$(3, 1)$ 最终结果均为 4）。
   4. 因此，【执行两次 $rand7()$ 相加，将 $[1, 10]$ 范围内的数进行返回，否则一直重试】的做法是错误的。
2. 因为**每次执行 $rand7()$ 都可以看做是一次独立事件**，因此我们**可以将两次 $rand7()$ 的结果看作是生成 7 进制的两位**，**从而实现每个数值都唯一对应了一种随机值的组合**（等概率），例如：
   1. 设随机执行两次 $rand7()$ 得到的结果分别是 4、7。
   2. 由于我们是要 7 进制的数，因此可以先对 $rand7()$ 的执行结果进行-1 操作，将输出域偏移到 $[0, 6]$（仍为等概率），即得到 3、6，最终得到的数值是 63（7 进制）。
   3. 该数值唯一对应了我们的随机值组合方案，反过来随机值组合方案也唯一对应一个 7 进制的数值。
3. **根据「进制转换」的相关知识**，**如果我们存在一个 $randK()$ 的函数**，**对其执行 $n$ 次**，**我们能够等概率产生 $[0, K^n - 1]$ 范围内的数值**。
4. 本题中，**执行一次 $rand7()$ 只能产生 $[0, 6]$ 范围内的数值**，**不足 10 个**，而**执行 2 次 $rand7()$ 的话则能产生 $[0, 48]$ 范围内的数值**，**足够 10 个**，且**等概率**，因此我们**只需要判定生成的值是否为 $[1, 10]$ 即可**，**如果是的话直接返回**，**否则一直重试**。
5. 在上述的解法中，**范围 $[0, 48]$ 中**，**只有 $[1, 10]$ 范围内的数据会被接受返回**，**其余情况均被拒绝重试**，为了**尽可能少的调用 $rand7()$ 方法**，我们**可以从 $[0, 48]$ 中取与 $[1, 10]$ 成倍数关系的数**，**来进行转换**，因此我们**可以取 $[0, 48]$ 中的 $[1, 40]$ 范围内的数来代指 $[1, 10]$**，首先**在 $[0, 48]$ 中取 $[1, 40]$ 仍为等概率**，其次**形如 $x1$ 的数值有 4 个**，**分比为 1**、**11**、**21**、**31**，**形如 $x2$ 的数值有 4 个**，**分别为 2**、**12**、**22**、**32**...，因此**最终结果仍为等概率**。

## 3 参考代码

```java
public int rand10() {
    while (true) {
        int ans = (rand7() - 1) * 7 + (rand7() - 1);
        if (ans >= 1 && ans <= 40) return ans % 10 + 1;
    }
}
```

## 参考文献

1. [470. 用 Rand7() 实现 Rand10()](https://leetcode-cn.com/problems/implement-rand10-using-rand7)。
2. [【宫水三叶】k 进制诸位生成 + 拒绝采样](https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/gong-shui-san-xie-k-jin-zhi-zhu-wei-shen-zmd4)。