470. 用 Rand7() 实现 Rand10()
方法一：拒绝采样
思路与算法
我们可以用拒绝采样的方法实现 \textit{Rand10()}Rand10()。在拒绝采样中，如果生成的随机数满足要求，那么就返回该随机数，否则会不断生成，直到生成一个满足要求的随机数为止。
我们只需要能够满足等概率的生成 1010 个不同的数即可，具体的生成方法可以有很多种，比如我们可以利用两个 \textit{Rand7()}Rand7() 相乘，我们只取其中等概率的 1010 个不同的数的组合即可，当然还有许多其他不同的解法，可以利用各种运算和函数的组合等方式来实现。
比如我们可以利用两个\textit{Rand7()}Rand7()相乘，分别可以得到结果如下：
1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 4 6 8 10 12 14
3 3 6 9 12 15 18 21
4 4 8 12 16 20 24 28
5 5 10 15 20 25 30 35
6 6 12 18 24 30 36 42
7 7 14 21 28 35 42 49
我们可以得到每个数生成的概率为:
1 2 3 4 5 6 7 8 9
P 1/49 2/49 2/49 3/49 2/49 4/49 2/49 2/49 4/49
10 12 14 15 16 18 20 21 24
P 2/49 1/49 2/49 2/49 2/49 1/49 2/49 2/49 2/49
25 28 30 35 36 42 49
P 1/49 2/49 2/49 2/49 1/49 2/49 1/49
我们可以从中挑选 1010个等概率的数即可。
题目中要求尽可能的减少 \textit{Rand7()}Rand7() 的调用次数，则我们应该尽量保证生成的每个不同的数的生成概率尽可能的大，即调用 \textit{Rand7()}Rand7() 期望次数尽可能的小。
我们可以调用两次 \textit{Rand7()}Rand7()，那么可以生成 [1, 49][1,49] 之间的随机整数，我们只用到其中的前 4040 个用来实现 \textit{Rand10()}Rand10()，而拒绝剩下的 99 个数，如下图所示。
我们可以看到表中的 [1,49][1,49] 每个数生成的概率为 \frac{1}{49}
49
1
。我们实际上只取 [1,40][1,40] 这前 4040 个数，转化为 [1,10][1,10] 时，这 1010 个数中每个数的生成概率则为 \frac{4}{49}
49
4
。
代码
C++JavaC#JavaScriptGolangPython3
class Solution:
def rand10(self) -> int:
while True:
row = rand7()
col = rand7()
idx = (row - 1) * 7 + col
if idx <= 40:
return 1 + (idx - 1) % 10
复杂度分析
时间复杂度：期望时间复杂度为 O(1)O(1)，但最坏情况下会达到 O(\infty)O(∞)（一直被拒绝）。
空间复杂度：O(1)O(1)。
进阶问题
函数调用次数的期望：我们来分析这种方法在平均情况下需要调用 \textit{Rand7()}Rand7() 的次数。我们称连续调用两次 \textit{Rand7()}Rand7() 为一轮，在第一轮中，有 \frac{40}{49}
49
40
的概率被接受，而有 \frac{9}{49}
49
9
的概率被拒绝，进入第二轮随机；第二轮有 (\frac{9}{49})^{2}(
49
9
)
2
被拒绝,由此推理我们可以知道第nn轮被拒绝的概率为 (\frac{9}{49})^{n}(
49
9
)
n
。因此调用 \textit{Rand7()}Rand7() 的期望次数为：
\begin{aligned} E(\text{# calls}) &= 2 + 2 \cdot \frac{9}{49} + 2 \cdot (\frac{9}{49})^2 + \ldots\ &= 2 \sum_{n=0}^\infty (\frac{9}{49})^n\ &= 2 \cdot \frac{1}{1 - \frac{9}{49}}\ &= 2.45 \end{aligned}
E(# calls)
=2+2⋅
49
9
+2⋅(
49
9
)
2
+…
=2
n=0
∑
∞
(
49
9
)
n
=2⋅
1−
49
9
1
=2.45
减少 \textit{Rand7()}Rand7() 的调用次数: 我们减小随机被拒绝的概率，从而减小 \textit{Rand7()}Rand7() 的调用次数的期望，即可减少 \textit{Rand7()}Rand7() 的平均调用次数。
我们可以通过合理地使用被拒绝的采样，从而对方法一进行优化。在方法一中，我们生成 [1, 49][1,49] 的随机数，若生成的随机数 xx 在 [41, 49][41,49] 中，我们则拒绝 xx。然而在 xx 被拒绝的情况下，我们得到了一个 [1, 9][1,9] 的随机数，如果再调用一次 \textit{Rand7()}Rand7()，那么就可以生成 [1, 63][1,63] 的随机数。我们保留 [1, 60][1,60] 并拒绝 [61, 63][61,63]：这是 [1, 3][1,3] 的随机数。我们继续调用 Rand7()Rand7()，生成 [1, 21][1,21] 的随机数，保留 [1, 20][1,20] 并拒绝 [1][1]。此时 [1][1] 已经没有任何用处，若出现了拒绝 11 的情况，我们就重新开始生成 [1, 49][1,49] 的随机数。我们可以算它的期望如下：
\begin{aligned} E(\text{# calls}) &= 2 + 1 \cdot \frac{9}{49} + 1 \cdot \frac{9}{49} \cdot \frac{3}{63} + 2 \cdot \frac{9}{49} \cdot \frac{3}{63} \cdot \frac{1}{21} + \ldots \ &= (2 + \frac{9}{49} + \frac{9}{49} \cdot \frac{3}{63}) \cdot\frac{1}{1-\frac{9}{49} \cdot \frac{3}{63} \cdot \frac{1}{21} }\ &\approx 2.19333 \end{aligned}
E(# calls)
=2+1⋅
49
9
+1⋅
49
9
⋅
63
3
+2⋅
49
9
⋅
63
3
⋅
21
1
+…
=(2+
49
9
+
49
9
⋅
63
3
)⋅
1−
49
9
⋅
63
3
⋅
21
1
1
≈2.19333
参考代码
C++JavaC#JavaScriptGolangPython3
class Solution:
def rand10(self) -> int:
while True:
a = rand7()
b = rand7()
idx = (a - 1) * 7 + b
if idx <= 40:
return 1 + (idx - 1) % 10
a = idx - 40
b = rand7()
# get uniform dist from 1 - 63
idx = (a - 1) * 7 + b
if idx <= 60:
return 1 + (idx - 1) % 10
a = idx - 60
b = rand7()
# get uniform dist from 1 - 21
idx = (a - 1) * 7 + b
if idx <= 20:
return 1 + (idx - 1) % 10
Part 1
假设已知rand2()可以均匀的生成[1,2]的随机数，现在想均匀的生成[1,4]的随机数，该如何考虑？
我想如果你也像我一样第一次接触这个问题，那么很可能会这么考虑——令两个rand2()相加，再做一些必要的边角处理。如下：
rand2() + rand2() = ? ==> [2,4]
1 + 1 = 2
1 + 2 = 3
2 + 1 = 3
2 + 2 = 4
// 为了把生成随机数的范围规约成[1,n]，于是在上一步的结果后减1
(rand2()-1) + rand2() = ? ==> [1,3]
0 + 1 = 1
0 + 2 = 2
1 + 1 = 2
1 + 2 = 3
可以看到，使用这种方法处理的结果，最致命的点在于——其生成的结果不是等概率的。在这个简单的例子中，产生2的概率是50%，而产生1和3的概率则分别是25%。原因当然也很好理解，由于某些值会有多种组合，因此仅靠简单的相加处理会导致结果不是等概率的。
因此，我们需要考虑其他的方法了。
仔细观察上面的例子，我们尝试对 (rand2()-1) 这部分乘以 2，改动后如下：
(rand2()-1) × 2 + rand2() = ? ==> [1,3]
0 + 1 = 1
0 + 2 = 2
2 + 1 = 3
2 + 2 = 4
神奇的事情发生了，奇怪的知识增加了。通过这样的处理，得到的结果恰是[1,4]的范围，并且每个数都是等概率取到的。因此，使用这种方法，可以通过rand2()实现rand4()。
也许这么处理只是我运气好，而不具有普适性？那就多来尝试几个例子。比如：
(rand9()-1) × 7 + rand7() = result
a b
为了表示方便，现将rand9()-1表示为a，将rand7()表示为b。计算过程表示成二维矩阵，如下：
可以看到，这个例子可以等概率的生成[1,63]范围的随机数。再提炼一下，可以得到这样一个规律：
已知 rand_N() 可以等概率的生成[1, N]范围的随机数
那么：
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数
即实现了 rand_XY()
Part 2
那么想到通过rand4()来实现rand2()呢？这个就很简单了，已知rand4()会均匀产生[1,4]的随机数，通过取余，再加1就可以了。如下所示，结果也是等概率的。
rand4() % 2 + 1 = ?
1 % 2 + 1 = 2
2 % 2 + 1 = 1
3 % 2 + 1 = 2
4 % 2 + 1 = 1
事实上，只要rand_N()中N是2的倍数，就都可以用来实现rand2()，反之，若N不是2的倍数，则产生的结果不是等概率的。比如：
rand6() % 2 + 1 = ?
1 % 2 + 1 = 2
2 % 2 + 1 = 1
3 % 2 + 1 = 2
4 % 2 + 1 = 1
5 % 2 + 1 = 2
6 % 2 + 1 = 1
rand5() % 2 + 1 = ?
1 % 2 + 1 = 2
2 % 2 + 1 = 1
3 % 2 + 1 = 2
4 % 2 + 1 = 1
5 % 2 + 1 = 2
Part 3
ok，现在回到本题中。已知rand7()，要求通过rand7()来实现rand10()。
有了前面的分析，要实现rand10()，就需要先实现rand_N()，并且保证N大于10且是10的倍数。这样再通过rand_N() % 10 + 1 就可以得到[1,10]范围的随机数了。
而实现rand_N()，我们可以通过part 1中所讲的方法对rand7()进行改造，如下：
(rand7()-1) × 7 + rand7() ==> rand49()
但是这样实现的N不是10的倍数啊！这该怎么处理？这里就涉及到了“拒绝采样”的知识了，也就是说，如果某个采样结果不在要求的范围内，则丢弃它。基于上面的这些分析，再回头看下面的代码，想必是不难理解了。
class Solution extends SolBase {
public int rand10() {
while(true) {
int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数
if(num <= 40) return num % 10 + 1; // 拒绝采样，并返回[1,10]范围的随机数
}
}
}
Part 4: 优化
这部分具体的代码是参考官方题解的，不过是我自己在理解了part 1和part 2之后才看懂的，一开始看真不知道为什么（/(ㄒoㄒ)/~~…
根据part 1的分析，我们已经知道(rand7() - 1) * 7 + rand7() 等概率生成[1,49]范围的随机数。而由于我们需要的是10的倍数，因此，不得不舍弃掉[41, 49]这9个数。优化的点就始于——我们能否利用这些范围外的数字，以减少丢弃的值，提高命中率总而提高随机数生成效率。
class Solution extends SolBase {
public int rand10() {
while(true) {
int a = rand7();
int b = rand7();
int num = (a-1)*7 + b; // rand 49
if(num <= 40) return num % 10 + 1; // 拒绝采样
a = num - 40; // rand 9
b = rand7();
num = (a-1)*7 + b; // rand 63
if(num <= 60) return num % 10 + 1;
a = num - 60; // rand 3
b = rand7();
num = (a-1)*7 + b; // rand 21
if(num <= 20) return num % 10 + 1;
}
}
}
进阶
降低对 rand7 的调用次数
我们发现，在上述解法中，范围 [0, 48][0,48] 中，只有 [1, 10][1,10] 范围内的数据会被接受返回，其余情况均被拒绝重试。
为了尽可能少的调用 rand7 方法，我们可以从 [0, 48][0,48] 中取与 [1, 10][1,10] 成倍数关系的数，来进行转换。
我们可以取 [0, 48][0,48] 中的 [1, 40][1,40] 范围内的数来代指 [1, 10][1,10]。
首先在 [0, 48][0,48] 中取 [1, 40][1,40] 仍为等概率，其次形如 x1x1 的数值有 44 个（11、1111、2121、3131），形如 x2x2 的数值有 44 个（22、1212、2222、3232）… 因此最终结果仍为等概率。
代码：
Java
class Solution extends SolBase {
public int rand10() {
while (true) {
int ans = (rand7() - 1) * 7 + (rand7() - 1); // 进制转换
if (1 <= ans && ans <= 40) return ans % 10 + 1;
}
}
}
时间复杂度：期望复杂度为 O(1)O(1)，最坏情况下为 O(\infty)O(∞)
空间复杂度：O(1)O(1)
计算 rand7 的期望调用次数
在 [0, 48][0,48] 中我们采纳了 [1, 40][1,40] 范围内的数值，即以调用两次为基本单位的话，有 \frac{40}{49}
49
40
的概率被接受返回（成功）。
成功的概率为 \frac{40}{49}
49
40
，那么需要触发成功所需次数（期望次数）为其倒数 \frac{49}{40} = 1.225
40
49
=1.225，每次会调用两次 rand7，因而总的期望调用次数为 1.225 * 2 = 2.451.225∗2=2.45 。
官方题解或者其他解法都是很棒的思路，但是他们都舍弃太多random出来的数了，导致最终的调用期望次数很高。而理论上最佳的期望为log_{7}10 = 1.183log
7
10=1.183，而这个期望正是需要lee215的题解
的7的次方思路的。
我的理解哈。7^{19} = 113988951853731437
19
=11398895185373143。就如同生成49舍弃40-48时一样，这里舍弃后能保证11398895185373140种情况生成了（至少）一个随机数，概率是99.99999999999997%。而且其中10000000000000000以下的数是一个16位的10进制数，而这16位数每位数0-9的概率是一致的，也就是87.73%的概率生成了16个随机数。
没有特别理解清楚这个解法，希望有大佬指教。
代码
Python3Java
class Solution:
cache, upper = 0, 1
def rand10(self):
while self.upper < 10**9:
self.cache, self.upper = self.cache * 7 + rand7() - 1, self.upper * 7
res = self.cache % 10 + 1
self.cache, self.upper = cache // 10, upper // 10
return res
定理：若rand_n()能等概率生成1到n的随机整数，则有(rand_n() - 1) * n + rand_n()能
等概率生成1到n * n的随机整数。
解释： rand()7能等概率生成1~7,
rand7() - 1能等概率生成0~6,
(rand7() - 1) * 7能等概率生成{0, 7, 14, 21, 28, 35, 42},
(rand7() - 1) * 7 + rand7()能等概率生成1~49。
class Solution {
public:
int rand10() {
while (true)
{
int x = rand7();
int num = (x - 1) * 7 + rand7(); //rand7()每次调用的值都不同，故不要用变量来存
if (num <= 40) return num % 10 + 1; //大于 40 拒绝采样，
x = num - 40; //此时 x = rand9()
num = (x - 1) * 7 + rand7(); // 8 * 7 + 7 = 63
if (num <= 60) return num % 10 + 1; //大于 60 拒绝采样
x = num - 60; //此时 x = rand3()
num = (x - 1) * 7 + rand7(); // 2 * 7 + 7 = 21
if (num <= 20) return num % 10 + 1; //大于 20 拒绝采样
}
}
};
当然到最后一步还可以继续写下去，但是没必要了，最后一步在 21 中能取到 21 的概率太低，不值得为这个概率再去调用一次rand7()做计算了。此时rand7()的调用次数可以说已经达到了极小值点，再继续下去反而会增加rand7()的调用次数。