随机

约 365 个字 37 行代码 预计阅读时间 2 分钟

在算法竞赛中，有时需要随机数，或者随机序列等

随机数生成器(random number generator)

不建议使用 < cstdlib > 的rand()，值域小 $[0,32767]$，强行扩大值域破坏随机性；执行速度慢。

在Cpp11中 < random > 提供了很多更好的随机数生成器，这里介绍 mt19937,mt19937_64,uniform_int_distribution

mt19937、mt19937_64 值域大，周期长 $(2^{19937}-1)$，速度快。前者产生32位(unsigned int)随机数，后者产生64位(unsigned long long)随机数。如果用signed存储会有负数。

随机数产生需要种子，当种子固定时产生的随机数固定，所以需要变化的种子，这里介绍 < chrono > 的chrono::steady_clock::now().time_since_epoch().count(), < random > 的random_device{}()。

前者与系统当前时间相关。

后者也是一个随机数生成器，与硬件设备相关，由于需要访问硬件导致速度慢，而且不适用产生大量均匀随机数，所以[3]说专门用来播种。[1]评论区和[2]中提到的”产生相同随机数“问题，是 MinGW 的旧版本漏洞 338，GCC 9.2 起修复

#include<chrono>
#include<iostream>
#include<random>
using namespace std;
int main()
{
    mt19937 rng1(chrono::steady_clock::now().time_since_epoch().count());
    mt19937 rng2(random_device{}());
    cout<<rng1()<<" "<<rng2();
}

当需要产生区间内随机数，用mt19937取模会导致不均匀，所以使用uniform_int_distribution，特别地，需要两次种子才能使随机数不重复

#include<iostream>
#include<random>
#include<chrono>
using namespace std;
int main()
{
    mt19937 seed(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<> rng(114,514);
    for(int i=0;i<10;++i)
        cout<<rng(seed)<<"\n";
}

随机序列

由于random_shuffle使用了rand，所以不可靠，你可以使用 < algorithm > 的shuffle搭配mt19937

#include<iostream>
#include<random>
#include<chrono>
#include<algorithm>
using namespace std;
const int N=50;
int main()
{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> permutation(N);
    for (int i = 0; i < N; i++)
        permutation[i] = i;
    shuffle(permutation.begin(), permutation.end(), rng);
    for (int i = 0; i < N; i++)
        cout<<permutation[i]<<"\n";
}