rnd.hpp¶
Seeded random-number helpers for tests and randomized algorithms.
提供可设种子的随机数生成器；用于随机化算法、哈希种子和可复现压力测试。
Implementation¶
#ifndef NOYA_RANDOM_HPP
#define NOYA_RANDOM_HPP 1
/// @complexity Time: O(n) per generated permutation/tree; O(1) scalar draws.
/// Space: O(n) returned data.
/// @brief Random permutation, hash-value, and rooted-tree generators backed by
/// a shared 64-bit Mersenne Twister.
#include <algorithm>
#include <ctime>
#include <numeric>
#include <random>
#include <vector>
namespace noya {
using ull = unsigned long long;
namespace internal {
inline std::mt19937_64 &gen_values() {
static std::mt19937_64 gen(time(0));
return gen;
}
} // namespace internal
inline std::vector<int> random_permutation(int N) {
std::vector<int> p(N);
std::iota(p.begin(), p.end(), 0);
std::shuffle(p.begin(), p.end(), internal::gen_values());
return p;
}
inline std::vector<ull> random_hash_values(int N) {
std::vector<ull> X(N);
std::generate(X.begin(), X.end(), internal::gen_values());
return X;
}
inline std::vector<std::vector<int>> random_tree(int N) {
std::vector<std::vector<int>> g(N);
for (int i = 1; i < N; i++) {
int p = internal::gen_values()() % i;
g[p].push_back(i);
}
return g;
}
} // namespace noya
#endif // NOYA_RANDOM_HPP
#include <algorithm>
#include <ctime>
#include <numeric>
#include <random>
#include <vector>
/// @complexity Time: O(n) per generated permutation/tree; O(1) scalar draws.
/// Space: O(n) returned data.
/// @brief Random permutation, hash-value, and rooted-tree generators backed by
/// a shared 64-bit Mersenne Twister.
namespace noya {
using ull = unsigned long long;
namespace internal {
inline std::mt19937_64 &gen_values() {
static std::mt19937_64 gen(time(0));
return gen;
}
} // namespace internal
inline std::vector<int> random_permutation(int N) {
std::vector<int> p(N);
std::iota(p.begin(), p.end(), 0);
std::shuffle(p.begin(), p.end(), internal::gen_values());
return p;
}
inline std::vector<ull> random_hash_values(int N) {
std::vector<ull> X(N);
std::generate(X.begin(), X.end(), internal::gen_values());
return X;
}
inline std::vector<std::vector<int>> random_tree(int N) {
std::vector<std::vector<int>> g(N);
for (int i = 1; i < N; i++) {
int p = internal::gen_values()() % i;
g[p].push_back(i);
}
return g;
}
} // namespace noya