构造 RandX()

由 randA() 实现 randB()：万能构造法

randA() 构造 randB() 时，需要找一个最大质因子不超过 A 的数 n (n>=B），然后对 n 分解质因子就能找到每个采样需要取多少种结果。实际到具体数字时，可以把部分质因子合并成不超过 A 的数，从而减少采样次数。

举个具体例子，如何用 rand7() 来构造 rand10()

确定采样参数

• 步骤 1：选择一个合适的数 n

我们选择 n = 30，因为它大于或等于 10，并且它的最大质因子是 5，不超过 7。

• 步骤 2：对 n 进行质因子分解

将 30 分解为质因子的乘积形式：

$$ 30 = 2^{1 \times 3}1 \times 5^1 $$

• 步骤 3：确定采样次数和结果数量

根据质因子分解的结果，我们需要进行 3 次采样，每次采样的结果数量分别为 2、3 和 5。（分别对应三个质因子）

进行采样

我们将进行 3 次采样，每次采样使用 rand7() 函数来生成一个介于 1 和 7 之间的随机数。

1. 第一次采样
   • 使用 rand7() 来生成一个随机数，如果结果在 [1, 2] 范围内，则将其作为第一次采样的结果。否则，重新采样。

   1 2 3 4 5

   int first; while (true) { first = rand7(); if (first <= 2) break; }

2. 第二次采样
   • 使用 rand7() 来生成一个随机数，如果结果在 [1, 3] 范围内，则将其作为第一次采样的结果。否则，重新采样。

   1 2 3 4 5

   int second; while (true) { second = rand7(); if (second <= 3) break; }

3. 第三次采样
   • 使用 rand7() 来生成一个随机数，如果结果在 [1, 5] 范围内，则将其作为第一次采样的结果。否则，重新采样。

   1 2 3 4 5

   int third; while (true) { third = rand7(); if (third <= 5) break; }

组合结果

将每次采样的结果组合起来，得到一个长度为 30 的序列。具体来说：

• first 的取值范围是 [1, 2]，总共有 2 种可能。
• second 的取值范围是 [1, 3]，总共有 3 种可能。
• third 的取值范围是 [1, 5]，总共有 5 种可能。

我们通过三次采样得到三个值：first、second 和 third。我们的目标是将这三个值组合成一个唯一的索引，这个索引应该对应于一个长度为 30 的序列中的一个位置。

这三个值的所有可能组合数是：$ 2\times 3\times 5 = 30 $， 这正好等于我们预定义的序列长度。

映射

为了将这三个值组合成一个唯一的索引，我们需要为每个值分配一个权重，使得它们的组合能够覆盖从 1 到 30 的所有整数。

公式为：

$$ index = (first - 1)\times 3 \times 5 + (second - 1)\times 5 + (third - 1) + 1 $$

代表：

$$[0, 1]\times 3\times 5 \rightarrow [0, 15]$$ $$[0, 2]\times 5 \rightarrow [0, 10]$$ $$[0, 4] + 1 \rightarrow [1, 5]$$

完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int rand10() {
    int first, second, third;
    while (true) {
        first = rand7(); // 第一次采样
        if (first <= 2) break; // 如果结果在 [1, 2] 范围内，则退出循环
    }
    while (true) {
        second = rand7(); // 第二次采样
        if (second <= 3) break; // 如果结果在 [1, 3] 范围内，则退出循环
    }
    while (true) {
        third = rand7(); // 第三次采样
        if (third <= 5) break; // 如果结果在 [1, 5] 范围内，则退出循环
    }
    // 将结果组合并映射到 [1, 10] 范围内
    int index = (first - 1) * 3 * 5 + (second - 1) * 5 + (third - 1) + 1;
    if (index <= 10) return index;
    else return rand10(); // 如果结果超出范围，则重新采样
}