random/shuffle.hpp

• View this file on GitHub
• Last update: 2023-02-17 09:47:57+09:00
• Include: #include "random/shuffle.hpp"

Depends on

• random/base.hpp

Required by

• geo/closest_pair.hpp
• geo/minimum_enclosing_circle.hpp
• random/random_graph.hpp

Verified with

• test/aoj/CGL_5_A.test.cpp
• test/mytest/count_K4.test.cpp
• test/mytest/count_P3P4P5.test.cpp
• test/mytest/count_clique.test.cpp
• test/mytest/count_indep_set.test.cpp
• test/mytest/find_C4.test.cpp
• test/mytest/find_even_cycle.test.cpp
• test/mytest/find_odd_cycle.test.cpp
• test/mytest/incremental_scc.test.cpp
• test/mytest/matching_line_graph.test.cpp
• test/mytest/matching_ve.test.cpp
• test/mytest/remove_one_edge.test.cpp
• test/mytest/remove_one_vertex.test.cpp
• test/mytest/st_numbering.test.cpp
• test/mytest/tree_walk_gf.test.cpp
• test_atcoder/abc151f.test.cpp

Code

#include "random/base.hpp"

template <typename T>
void shuffle(vc<T>& A) {
  FOR(i, len(A)) swap(A[i], A[RNG(0, i + 1)]);
}

#line 2 "random/base.hpp"

u64 RNG_64() {
  static uint64_t x_
      = uint64_t(chrono::duration_cast<chrono::nanoseconds>(
                     chrono::high_resolution_clock::now().time_since_epoch())
                     .count())
        * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 2 "random/shuffle.hpp"

template <typename T>
void shuffle(vc<T>& A) {
  FOR(i, len(A)) swap(A[i], A[RNG(0, i + 1)]);
}

Back to top page