隨機函數

概述

要想使用隨機化技巧，前提條件是能夠快速生成隨機數。本文將介紹生成隨機數的常見方法。

隨機數與偽隨機數

説一個單獨的數是「隨機數」是無意義的，所以以下我們都默認討論「隨機數列」，即使提到「隨機數」，指的也是「隨機數列中的一個元素」。

現有的計算機的運算過程都是確定性的，因此，僅憑藉算法來生成真正 不可預測、不可重複 的隨機數列是不可能的。

然而在絕大部分情況下，我們都不需要如此強的隨機性，而只需要所生成的數列在統計學上具有隨機數列的種種特徵（比如均勻分佈、互相獨立等等）。這樣的數列即稱為 偽隨機數 序列。

隨機數與偽隨機數在實際生活和算法中的應用舉例：

抽樣調查時往往只需使用偽隨機數。這是因為我們本就只關心統計特徵。
網絡安全中往往要用到（比剛剛提到的偽隨機數）更強的隨機數。這是因為攻擊者可能會利用可預測性做文章。
OI/ICPC 中用到的隨機算法，基本都只需要偽隨機數。這是因為，這些算法往往是通過引入隨機數來把概率引入複雜度分析，從而降低複雜度。這本質上依然只利用了隨機數的統計特徵。
某些隨機算法（例如 Moser 算法）用到了隨機數的熵相關的性質，因此必須使用真正的隨機數。

實現

`rand`

用於生成偽隨機數，缺點是比較慢，使用時需要 #include<cstdlib>。

調用 rand() 函數會返回一個 [0,RAND_MAX] 中的隨機非負整數，其中 RAND_MAX 是標準庫中的一個宏，在 Linux 系統下 RAND_MAX 等於 \(2^{31}-1\)。可以用取模來限制所生成的數的大小。

使用 rand() 需要一個隨機數種子，可以使用 srand(seed) 函數來將隨機種子更改為 seed，當然不初始化也是可以的。

同一程序使用相同的 seed 兩次運行，在同一機器、同一編譯器下，隨機出的結果將會是相同的。

有一個選擇是使用當前系統時間來作為隨機種子：srand(time(0))。

Warning

在 Windows 系統下 rand() 返回值的取值範圍為 \(\left[0,2^{15}\right)\)（即 RAND_MAX 等於 \(2^{15}-1\)），當需要生成的數不小於 \(2^{15}\) 時建議使用 (rand() << 15 | rand()) 來生成更大的隨機數。

關於 rand() 和 rand()%n 的隨機性：

C/C++ 標準並未關於 rand() 所生成隨機數的任何方面的質量做任何規定。
GCC 編譯器對 rand() 所採用的實現方式，保證了分佈的均勻性等基本性質，但具有低位週期長度短等明顯缺陷。（例如在筆者的機器上，rand()%2 所生成的序列的週期長約 \(2\cdot 10^6\)）
即使假設 rand() 是均勻隨機的，rand()%n 也不能保證均勻性，因為 [0,n) 中的每個數在 0%n,1%n,...,RAND_MAX%n 中的出現次數可能不相同。

預定義隨機數生成器

定義了數個特別的流行算法。如沒有特別説明，均定義於頭文件 <random>。

Warning

預定義隨機數生成器僅在於 C++11 標準²中開始使用。

mt19937

是一個隨機數生成器類，效用同 rand()，隨機數的範圍同 unsigned int 類型的取值範圍。

其優點是隨機數質量高（一個表現為，出現循環的週期更長；其他方面也都至少不遜於 rand()），且速度比 rand() 快很多。使用時需要 #include<random>。

mt19937 基於 32 位梅森纏繞器，由松本與西村設計於 1998 年³，使用時用其定義一個隨機數生成器即可：std::mt19937 myrand(seed)，seed 可不填，不填 seed 則會使用默認隨機種子。

mt19937 重載了 operator ()，需要生成隨機數時調用 myrand() 即可返回一個隨機數。

另一個類似的生成器是 mt19937_64，基於 64 位梅森纏繞器，由松本與西村設計於 2000 年，使用方式同 mt19937，但隨機數範圍擴大到了 unsigned long long 類型的取值範圍。

代碼示例

#include <ctime>
#include <iostream>
#include <random>

using namespace std;

int main() {
  mt19937 myrand(time(0));
  cout << myrand() << endl;
  return 0;
}

`minstd_rand0`

線性同餘算法由 Lewis、Goodman 及 Miller 發現於 1969，由 Park 與 Miller 於 1988 採納為「最小標準」。

計算公式如下，其中 \(A,C,M\) 為預定義常數。

\[ s_i\equiv s_{i-1}\times A+C\mod{M} \]

minstd_rand() 是較新的「最小標準」，為 Park、Miller 和 Stockmeyer 於 1993 推薦。

對於 minstd_rand0()，\(s\) 的類型取 32 位無符號整數，\(A\) 取 16807，\(C\) 取 0，\(M\) 取 2147483647。

對於 minstd_rand()，\(s\) 的類型取 32 位無符號整數，\(A\) 取 48271，\(C\) 取 0，\(M\) 取 2147483647。

`random_shuffle`

用於隨機打亂指定序列。使用時需要 #include<algorithm>。

使用時傳入指定區間的首尾指針或迭代器（左閉右開）即可：std::random_shuffle(first, last) 或 std::random_shuffle(first, last, myrand)

內部使用的隨機數生成器默認為 rand()。當然也可以傳入自定義的隨機數生成器。

關於 random_shuffle 的隨機性：

C++ 標準中要求 random_shuffle 在所有可能的排列中 等概率 隨機選取，但 GCC⁴編譯器並未嚴格執行。
GCC 中 random_shuffle 隨機性上的缺陷的原因之一，是因為它使用了 rand()%n 這樣的寫法。如先前所述，這樣生成的不是均勻隨機的整數。
原因之二，是因為 rand() 的值域有限。如果所傳入的區間長度超過 RAND_MAX，將存在某些排列 不可能 被產生¹。

Warning

random_shuffle 已於 C++14 標準中被棄用，於 C++17 標準中被移除。

`shuffle`

效用同 random_shuffle。使用時需要 #include<algorithm>。

區別在於必須使用自定義的隨機數生成器：std::shuffle(first, last, myrand)。

GCC⁴實現的 shuffle 符合 C++ 標準的要求，即在所有可能的排列中等概率隨機選取。

下面是用 rand() 及 random_shuffle() 編寫的一個數據生成器。生成數據為「ZJOI2012」災難的隨機小數據。

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>

int a[100];

int main() {
  srand(time(0));
  int n = rand() % 99 + 1;
  for (int i = 1; i <= n; i++) a[i] = i;
  std::cout << n << '\n';
  for (int i = 1; i <= n; i++) {
    std::random_shuffle(a + 1, a + i);
    int cnt = rand() % i;
    for (int j = 1; j <= cnt; j++) std::cout << a[j] << ' ';
    std::cout << 0 << '\n';
  }
}

下面是用 mt19937 及 shuffle() 編寫的同一個數據生成器。

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>

int a[100];

int main() {
  std::mt19937 rng(time(0));
  int n = rng() % 99 + 1;
  for (int i = 1; i <= n; i++) a[i] = i;
  std::cout << n << '\n';
  for (int i = 1; i <= n; i++) {
    std::shuffle(a + 1, a + i, rng);
    int cnt = rng() % i;
    for (int j = 1; j <= cnt; j++) std::cout << a[j] << ' ';
    std::cout << 0 << '\n';
  }
}

下面是隨機排列前十個正整數的一個實現。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>

int main() {
  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  std::random_device rd;
  std::mt19937 g(rd());

  std::shuffle(v.begin(), v.end(), g);

  std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\n";
}

非確定隨機數的均勻分佈整數隨機數生成器

random_device 是一個基於硬件的均勻分佈隨機數生成器，在熵池耗盡 前可以高速生成隨機數。該類在 C++11 定義，需要 random 頭文件。由於熵池耗盡後性能急劇下降，所以建議用此方法生成 mt19937 等偽隨機數的種子，而不是直接生成。

random_device 是非確定的均勻隨機位生成器，儘管若不支持非確定隨機數生成，則允許實現用偽隨機數引擎實現。目前筆者尚未接到報告稱 NOIP 評測機不支持基於硬件的均勻分佈隨機數生成。但出於保守考慮，建議使用該算法生成隨機數種子。

參考代碼如下。

#include <iostream>
#include <map>
#include <random>
#include <string>

int main() {
  std::random_device rd;
  std::map<int, int> hist;
  std::uniform_int_distribution<int> dist(0, 9);
  for (int n = 0; n < 20000; ++n) {
    ++hist[dist(rd)];  // 注意：僅用於演示：一旦熵池耗盡，
                       // 許多 random_device 實現的性能就急劇下滑
                       // 對於實踐使用， random_device 通常僅用於
                       // 播種類似 mt19937 的偽隨機數生成器
  }
  for (auto p : hist) {
    std::cout << p.first << " : " << std::string(p.second / 100, '*') << '\n';
  }
}

可能的輸出如下。

: ********************
: *******************
: ********************
: ********************
: ********************
: *******************
: ********************
: ********************
: *******************
: ********************

隨機數分佈

這裏介紹的是要求生成的隨機數按照一定的概率出現，如等概率，伯努利分佈，二項分佈，幾何分佈，標準正態（高斯）分佈。

具體類名請參見偽隨機數生成——隨機數分佈的列表。

實現

下面的程序模擬了一個六面體骰子。

#include <iostream>
#include <random>

int main() {
  std::random_device rd;   // 將用於為隨機數引擎獲得種子
  std::mt19937 gen(rd());  // 以播種標準 mersenne_twister_engine
  std::uniform_int_distribution<> dis(1, 6);

  for (int n = 0; n < 10; ++n)
    // 用 dis 變換 gen 所生成的隨機 unsigned int 到 [1, 6] 中的 int
    std::cout << dis(gen) << ' ';
  std::cout << '\n';
}

其他實現方法

有的時候我們需要實現自己的隨機數生成器。下面是一些常用的隨機數生成方法。

線性同餘隨機數生成器

利用下式來生成隨機數序列 \(\{R_i\}\)：

\[ R_{i+1} = (A \times R_i + B) \bmod P \]

其中 \(A,B,P\) 均為常數。

該方法實現難度低，但生成的隨機序列週期長度較短（週期最大為 \(P\)，但大多數情況下都會比 \(P\) 短）。

參考實現

#include <iostream>
using namespace std;

struct myrand {
  int A, B, P, x;

  myrand(int A, int B, int P) {
    this->A = A;
    this->B = B;
    this->P = P;
  }

  int next() { return x = (A * x + B) % P; }  // 生成隨機序列的下一個隨機數
};

myrand rnd(3, 5, 97);  // 初始化一個隨機數生成器

int main() {
  int x = rnd.next();
  cout << x << endl;
  return 0;
}

時滯斐波那契隨機數生成器

利用下式來生成隨機數序列 \(\{R_i\}\)（其中 \(0 < j < k\)）：

\[ R_i \equiv R_{i-j} \star R_{i-k} \bmod P \]

這裏的 \(P\) 通常取 \(2\) 的冪（常用 \(2^{32}\) 或 \(2^{64}\)），\(\star\) 表示二元運算符，可以使用加法，減法，乘法，異或。

該方法較傳統的線性同餘隨機數生成器而言，擁有更長的週期，但隨機性受初始條件影響較大。

參考實現

#include <iostream>
#include <vector>
using namespace std;

struct myrand {
  vector<unsigned> vec;
  int l, j, k, cur;

  myrand(int l, int j, int k) {
    this->l = l;
    this->j = j;
    this->k = k;
    cur = 0;
    for (int i = 0; i < l; i++) {
      vec.push_back(rand());  // 先用其他方法生成隨機序列中的前幾個元素
    }
  }

  unsigned next() {
    vec[cur] = vec[(cur - j + l) % l] * vec[(cur - k + l) % l];
    // 這裏用 unsigned 類型是為了實現自動對 2^32 取模
    return vec[cur++];
  }
};

myrand rnd(11, 4, 7);

int main() {
  unsigned x = rnd.next();
  cout << x << endl;
  return 0;
}

參考資料與註釋

Don't use rand(): a guide to random number generators in C++ ↩
偽隨機數生成 - cppreference.com ↩
Mersenne Twister algorithm ↩
版本號為 GCC 9.2.0 ↩↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用