random/rand_perm.cpp

View this file on GitHub
Last update: 2021-12-17 09:20:39+09:00

Depends on

Code

#pragma once
#include <numeric>
#include <vector>
#include "shuffle_vec.cpp"

template <class T> std::vector<T> rand_perm(const int n, const T& first = 0) {
    std::vector<T> p(n);
    std::iota(p.begin(), p.end(), first);
    shuffle_vec(p);
    return p;
}

#line 2 "random/rand_perm.cpp"
#include <numeric>
#include <vector>
#line 2 "random/shuffle_vec.cpp"
#include <algorithm>
#include <random>
#line 2 "random/xorshift.cpp"
#include <chrono>
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 5 "random/xorshift.cpp"

u64 xorshift() {
    static u64 state = std::chrono::system_clock::now().time_since_epoch().count();
    state ^= state << 7;
    state ^= state >> 9;
    return state;
}
#line 6 "random/shuffle_vec.cpp"

template <class C> void shuffle_vec(C& v) {
    static std::default_random_engine gen(xorshift());
    std::shuffle(v.begin(), v.end(), gen);
}
#line 5 "random/rand_perm.cpp"

template <class T> std::vector<T> rand_perm(const int n, const T& first = 0) {
    std::vector<T> p(n);
    std::iota(p.begin(), p.end(), first);
    shuffle_vec(p);
    return p;
}