一、摘要
随机数可以应用在很多场景下如游戏抽卡、抽奖、场景生成、洗牌，歌曲app中的随机播放，社交app中的匹配等以及随机化算法。
以下是针对C中随机函数rand、C++random库使用的总结，以及一些随机应用例子
二、C/C++ 中的rand 函数
使用时需要引入头文件<stdlib.h>
该函数返回一个在[0, RAND_MAX]范围内的数字，RAND_MAX该宏定义值取决于实现，至少为32767
使用rand()需要一个随机种子，可以使用srand(seed)来设置随机种子(这里的seed一般选择当前系统时间time(0))，当程序没有调用srand，会默认使用srand(1)来作为随机种子
rand函数使用到的随机数生成算法--线性同余方法
\[N_{j+1} = (A \quad *\quad N_j + B) (mod \quad M) \]可以看到当前的随机数，是根据上次随机数进行计算得到。因此同一程序使用相同的seed俩次运行，同一机器和编译器下，随机结果会是相同的。这样可以在程序应用中获得可再现的随机过程。
rand和srand伪代码实现，glibc rand源码实现
unsigned long _Randseed = 1; //默认随机种子为1
int rand(void) {
_Randseed = _Randseed * 1103515245 + 12345;
return ((unsigned int)(_Randseed >> 16) & RAND_MAX);
}
void srand(unsigned int seed) {
_Randseed = seed;
}
需要注意的是rand函数不是线程安全的，多个线程同时调用rand可能获得同样的结果：多线程rand获得一样结果原因
使用比较简单
#include <cstdlib>
#include <iostream>
int main(int argc, char**argv)
{
srand(time(nullptr));
//如果在应用程序中需要一个可重复的随机过程
//使用固定的seed作为srand参数
std::cout << "randmax: " << RAND_MAX << std::endl;
for(int i = 0; i < 10; i++)
{
std::cout << " " << rand();
}
std::cout << std::endl;
return 0;
}
三、C++random库
random库主要由随机数引擎(Random number engines)和随机数分布(Random number distributions)组成，使用时需要引入头文件 #include <random>。
使用随机数引擎生成一定范围内随机数，使用随机分布可以得到满足一定规律的分布（均匀分布，伯努利分布、泊松分布、正太分布、抽样分布）的随机数
3.1 随机数引擎
3.1.1 模板类
| 模板 | 作用 |
|---|---|
| linear_congruential_engine | 实现线性同余算法 速度适中 |
| mersenne_twister_engine | 实现 Mersenne twister算法 速度较慢, 具有最长非重复序列 |
| subtract_with_carry_engint | 实现滞后斐波那契算法, 速度最快 |
3.1.2 非确定性随机数
- std::random_device 是一个非确定性随机数生成器。通常被用作生成伪随机数器的种子。
3.1.3 一些预定义的随机数引擎
- minstd_rand0 / minstd_rand（C++11）//线性同余法生成随机数
#include <iostream>
#include <random>
//std::minstd_rand0
//定义：std：：linear_congruential_engine<std：：uint_fast32_t， 16807， 0， 2147483647>
int main(int argc, char**argv)
{
std::random_device rd;
unsigned int seed = rd();
std::minstd_rand0 gen(seed);
for(int i = 0; i < 10; i++)
{
std::cout << " " << gen();
}
return 0;
}
- mt19937 (32位)/ mt19937_64 （64 位）使用Mersenne twister算法生成随机数，随机效果最好
#include <iostream>
#include <random>
//std::mt19937
/*定义
std::mersenne_twister_engine<std::uint_fast32_t、32、624、397、31、
0x9908b0df,11,
0xffffffff,7,
0x9d2c5680,15,
0xefc60000,18,1812433253>
*/
int main(int argc, char**argv)
{
std::random_device rd;
unsigned int seed = rd();
std::mt19937 mt_r(seed);
for(int i = 0; i < 10; i++)
{
std::cout << " " << mt_r();
}
return 0;
}
- ranlux24_base/ranlux48_base 使用滞后斐波那契算法，与其他比较速度最快
#include <iostream>
#include <random>
//std::ranlux24_base
//std::subtract_with_carry_engine<std::uint_fast32_t, 24, 10, 24>
int main(int argc, char**argv)
{
std::random_device rd;
unsigned int seed = rd();
std::ranlux24_base r(seed);
for(int i = 0; i < 10; i++)
{
std::cout << " " << r();
}
return 0;
}
3.2 随机数分布
3.2.1 均匀分布
在闭区间[a, b]中返回一个整数i，i的概率为
\[P(i|a,b) = \frac{1}{(b-a)+1} \]使用方式
#include <iostream>
#include <random>
int main()
{
std::random_device rd;//非确定性随机数生成器
std::mt19937 gen(rd()); //使用Mersenne twister算法随机数生成器
std::uniform_int_distribution<> distrib(1, 6); //随机均匀分布[1,6]区间
//随机在闭区间[1,6]中返回一个数
for (int n = 0; n != 10; ++n)
std::cout << distrib(gen) << ' ';
std::cout << '\n';
}
3.2.1 伯努利分布(0-1分布)
\[p(b/p)= \left\{\begin{matrix} p, if \quad b \quad is \quad true \\ 1-p, if \quad b \quad is \quad false \end{matrix}\right. \]使用
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
int main()
{
std::random_device rd;
std::mt19937 gen(rd());
std::bernoulli_distribution d(0.25); //默认参数为0.5，返回true的概率
std::map<bool, int> hist;
for (int n = 0; n < 10000; ++n)
++hist[d(gen)];
std::cout << std::boolalpha;
for (auto const& [key, value] : hist)
std::cout << std::setw(5) << key << ' '
<< std::string(value / 500, '*') << '\n';
}
还有泊松、正太、抽样方式随机分布，更多查看
四、随机数相关
4.1 洗牌算法 Knuth_Durstenfeld_Shuffle，就地洗牌
打乱一个数组num[n]， 从后向前遍历，当前位置i，从[0, i-1]中随机选择一个元素与num[i]交换
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
Knuth_Durstenfeld_Shuffle 算法是通过交换原数组的元素来达到打乱效果，当不能修改原数组，需要返回洗牌后新数组，可以使用"inside-out" 算法
4.2 "inside-out" 洗牌算法，不修改原数组
从原数组source[n]返回打乱后数组a，从前往后遍历原数组，当前位置i，从[0,i-1]随机选值j，
当 \(j != i \quad a[i] =a[j]\) 然后将source[i]赋值给a[j]
To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based:
for i from 0 to n − 1 do
j ← random integer such that 0 ≤ j ≤ i
if j ≠ i
a[i] ← a[j]
a[j] ← source[i]
4.3 线段分割（红包随机、固定长度随机切割）
- 例子：生成 10 个随机数 （0, 100） 且最终 10 个随机数之和为 100（或者固定100面值随机10个红包）
线段分割：在一根1到100的数轴上，选取9个点，拿到10个线段，计算每个线段的长度
C++代码实现
#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
int main(int argc, char *argv[])
{
std::random_device device;
std::mt19937 mt(device());
std::uniform_int_distribution<> dis(1, 100);
std::set<int> random_val;
//需要进行去重，防止有重复的点。
while(random_val.size() < 9)
{
random_val.insert(dis(mt));
}
random_val.insert(0);
random_val.insert(100);
auto last = random_val.begin();
std::vector<int> ret;
for(auto cur = std::next(last); cur != random_val.end(); ++cur)
{
ret.push_back((*cur) - (*last));
last = cur;
}
int total = 0;
for(auto num : ret)
{
std::cout << " " << num;
total += num;
}
std::cout << std::endl;
std::cout << "totalnum: " << total << std::endl;
return 0;
}
//结果输出
// 24 11 38 2 1 1 4 8 2 9
//totalnum: 100
4.4 二倍均值法（提到红包随机，网上还提及这个算法）
每次在区间\([0.01,M/N*2-0.01]\)随机选取一个数，M是剩余红包金额，N红包剩余数量。
六、参考
- https://rgb-24bit.github.io/blog/2019/rand-misc.html
- https://en.cppreference.com/w/c/numeric/random/rand
- https://oi-wiki.org/misc/rand-technique/
- https://en.cppreference.com/w/cpp/numeric/random
- https://www.cnblogs.com/Critical-Thinking/p/16845446.html
- https://www.zhihu.com/question/22625187