随机数据的生成
前置知识 随机数的用法
注意下面的rnd代表一个的生成随机数据,你可以用随机数的用法 这里的两种风格的随机数封装类这一
cpp
//全局随机数据生成器
struct Random {
using ll = long long;
// std::random_device rd;
std::mt19937 engine;
std::uniform_int_distribution<long long> dis; // in [0,0x7fffffffffffffff]
Random() : engine{std::random_device{}()}
{}
//指定生成的随机数的范围
Random(ll l,ll r) :Random()
{ dis = std::uniform_int_distribution<long long> (l,r); }
ll operator()(){ return dis(engine); }
ll operator()(ll l,ll r){ return l == r ? l : dis(engine) % ( r-l+1 ) + l; }
} _rnd;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
整个代码整合到了一个文件,通过下面的命令下载
bash
wget https://rbook.roj.ac.cn//miniRainboyLib/randData.hpp
1
测试代码,查看代码,学习如何使用
bash
wget https://rbook.roj.ac.cn//miniRainboyLib/example/randData.cpp
1
或去这里查看本书配套的小型代码库miniRainboyLib
随机字符
cpp
const char char_sets[] = "abcdefghijklmnopqrstuvwxyzABCDEFHIJKLMNOPQRSTUVWXYZ";
inline char rand_char() {
return char_sets[_rnd(0,sizeof(char_sets) /sizeof(char_sets[0]))];
}
inline char rand_char(int l,int r) {
// r = std::max(r,sizeof(char_sets) /sizeof(char_sets[0]));
return char_sets[_rnd(l,r)];
}
inline char rand_lowchar() {
return rand_char(0,26-1);
}
inline char rand_upchar() {
return rand_char(26,52-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
随机字符串
TODO
工具函数
定义了一些输出的工具函数
cpp
const auto print_one = [](int n,bool nl= false){
std::cout << n <<" " ;
if(nl) std::cout << "\n";
};
const auto print_two = [](int l,int r){ std::cout << l <<" " << r << "\n";};
//输出两个点的同时,还输出一个随机的w
struct print_two_w {
int l,r;
print_two_w(): l(1),r(10) {}
print_two_w(int _l,int _r): l(_l),r(_r) {
if( l > r) std::swap(l,r);
}
void operator()(int _l,int _r){
std::cout << _l << " " << _r << " "
<< _rnd(l,r)
<< "\n";
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
随机序列
cpp
//生成n个[l,r]内的随机数
template<typename F>
void rand_seq(int n,int l,int r,F&& f){
for(int i=1;i<=n;++i){
f(_rnd(l,r));
}
}
void rand_seq(int n=10,int l=1,int r=10){
rand_seq(n,l,r,print_one);
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
无重复的随机序列
TODO,random_shuffle
随机树
原理,从第2个点开始,点i和随机点[1,i-1]连接,最后形成n条边的连通图,就是 树
cpp
// >>> 随机生成一个树
template<typename F>
void rand_tree(int n,F && f){
for(int i = 2 ;i<=n;i++ ){
f(_rnd(1,i-1),i);
}
}
void rand_tree(int n = 10){
rand_tree(n,print_two);
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
随机二叉树
同随机树的原理差不多,
设定两个集合
每一次点u都会去尝试连接{left}或{right}中的点,保证每个点不会超过2个孩子
cpp
template<typename F>
void rand_binary_tree(int n,F&& f){
std::set<int> left{1},right{1};
std::vector<int> v(n+1);
auto pic = [](std::set<int> & sets){
auto b = sets.begin();
std::advance(b, _rnd(0,sets.size()-1));
int ret = *b;
sets.erase(b);
return ret;
};
for(int i =2;i<=n;++i){
int chance = _rnd(1,100);
if( chance <= 50 && left.size() > 0 )
v[i] = pic(left);
else if( right.size() > 0)
v[i] = pic(right);
else
v[i] = pic(left);
left.insert(i);
right.insert(i);
}
for(int i=2;i<=n;i++)
f(v[i],i);
}
void rand_binary_tree(int n=10){
return rand_binary_tree(n,tree_out);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
随机图
cpp
// n个点m条边的随机图
template<typename F>
void rand_graph(int n,int m,F&& f){
std::set< std::pair<int,int> > _set; //防止重边
rand_tree(n, [&](int u,int v) {
f(u,v);
_set.emplace(u,v);
_set.emplace(v,u);
});
for(int i = n+1;i<=m;++i){
int u,v;
do {
u = _rnd(1,n), v = _rnd(1,n);
}while(u == v || _set.find(std::make_pair(u, v)) != _set.end());
_set.emplace(u,v);
_set.emplace(v,u);
f(u,v);
}
}
void rand_graph(int n=5,int m=10){
rand_graph(n,m,print_two);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
随机二分图
TODO
随机链图
TODO
随机🌼菊花图
TODO
随机蒲公英图
TODO
随机🌵仙人掌
TODO