隨機數生成算法：K進制逐位生成+拒絕采樣

轉自：【宮水三葉】k 進制諸位生成 + 拒絕采樣

基本分析

給定一個隨機生成 1 ~ 7 的函數，要求實現等概率返回 1 ~ 10 的函數。

首先需要知道，在輸出域上進行定量整體偏移，仍然滿足等概率，即要實現 0 ~ 6 隨機器，只需要在 rand7 的返回值上進行 -1 操作即可。

但輸出域的 拼接/疊加 并不滿足等概率。例如 rand7() + rand7() 會產生 [2, 14] 范圍內的數，但每個數并非等概率：

• 產生 2 的概率為：$\frac{1}{7}\times \frac{1}{7}=\frac{1}{49}$
• 產生 4 的概率為：$\frac{1}{7}\times \frac{1}{7}+\frac{1}{7}\times \frac{1}{7}+\frac{1}{7}\times \frac{1}{7}=\frac{3}{49}$

在 [2,14] 這 13 個數中，等概率的數不足 10 個。

因此，你應該知道「執行兩次 rand7 相加，將 [1, 10] 范圍內的數進行返回，否則一直重試」的做法是錯誤的。

k進制逐位生成 + 拒絕采樣

上述做法出現概率分布不均的情況，是因為兩次隨機值的不同組合「相加」的會出現相同的結果，比如 (1, 3)、(2, 2)、(3, 1) 最終結果均為 4。

結合每次執行 rand7 都可以看作一次獨立事件。我們可以將兩次 rand7 的結果看作生成 7 進制的兩位。從而實現每個數值都唯一對應了一種隨機值的組合（等概率），反之亦然。

舉個例子，設隨機執行兩次 rand7 得到的結果分別是 4（第一次）、7（第二次），由于我們是要 7 進制的數，因此可以先對 rand7 的執行結果進行 -1 操作，將輸出域偏移到 [0,6]（仍為等概率），即得到 3（第一次）和 6（第二次），最終得到的是數值 $(63{)}_7$ ，數值 $(63{)}_7$ 唯一對應了我們的隨機值組合方案，反過來隨機值組合方案也唯一對應一個 7 進制的數值。

那么根據「進制轉換」的相關知識，如果我們存在一個 randK 的函數，對其執行 $n$ 次，我們能夠等概率產生 $[0,K^n?1]$ 范圍內的數值。

回到本題，執行一次 rand7 只能產生 [0,6] 范圍內的數值，不足 10 個；而執行 2 次 rand7 的話則能產生 [0, 48] 范圍內的數值，足夠 10 個，且等概率。

我們只需要判定生成的值是否為題意的 [1, 10] 即可，如果是的話直接返回，否則一直重試。

代碼：

class Solution {
public:int rand10() {while (1) {int r71 = rand7();int r70 = rand7();int val = (r71 - 1) * 7 + r70 - 1;if (val >= 1 && val <= 10) return val;}}
};

• 時間復雜度：期望復雜度為 O(1)，最壞情況下為 O($\infty$)
• 空間復雜度：O(1)

進階

降低對 rand7 的調用次數

我們發現，在上述解法中，范圍 [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）… 因此最終結果仍為等概率。

代碼：

class Solution {
public:int rand10() {while (1) {int r71 = rand7();int r70 = rand7();int val = (r71 - 1) * 7 + r70 - 1;if (val >= 1 && val <= 40) return val % 10 + 1;}}
};

時間復雜度：期望復雜度為 O(1)，最壞情況下為 O($\infty$)
空間復雜度：O(1)

計算 rand7 的期望調用次數

在 [0, 48] 中我們采納了 [1, 40] 范圍內的數值，即以調用兩次為基本單位的話，有 $\frac{40}{49}$ 的概率被接受返回（成功）。

成功的概率為 $\frac{40}{49}$ ，那么觸發成功所需次數（期望次數）為其倒數 $\frac{49}{40}=1.225$，每次會調用兩次 rand7，因而總的期望調用次數為 $1.225?2=2.45$。