random/shuffle.hpp

• View this file on GitHub
• Last update: 2024-10-18 02:58:53+09:00
• Include: #include "random/shuffle.hpp"

Depends on

• random/base.hpp

Required by

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

Verified with

• test/1_mytest/count_K4.test.cpp
• test/1_mytest/count_P3P4P5.test.cpp
• test/1_mytest/count_clique.test.cpp
• test/1_mytest/count_indep_set.test.cpp
• test/1_mytest/extended_lichao.test.cpp
• test/1_mytest/extended_lichao_2.test.cpp
• test/1_mytest/find_C4.test.cpp
• test/1_mytest/find_cycle_minimum.test.cpp
• test/1_mytest/find_even_cycle.test.cpp
• test/1_mytest/find_odd_cycle.test.cpp
• test/1_mytest/incremental_scc.test.cpp
• test/1_mytest/matching_line_graph.test.cpp
• test/1_mytest/matching_ve.test.cpp
• test/1_mytest/nth_element_from_sorted_lists.test.cpp
• test/1_mytest/nth_element_from_sorted_matrix.test.cpp
• test/1_mytest/remove_one_edge.test.cpp
• test/1_mytest/remove_one_vertex.test.cpp
• test/1_mytest/rolling_hash_on_tree.test.cpp
• test/1_mytest/slope_super.test.cpp
• test/1_mytest/st_numbering.test.cpp
• test/1_mytest/tree_walk_gf.test.cpp
• test/2_library_checker/geometry/closest_pair.test.cpp
• test/2_library_checker/geometry/closest_pair_dc.test.cpp
• test/4_aoj/CGL_5_A.test.cpp

Code

#include "random/base.hpp"

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

#line 2 "random/base.hpp"

u64 RNG_64() {
  static u64 x_ = u64(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)) {
    int j = RNG(0, i + 1);
    if (i != j) swap(A[i], A[j]);
  }
}

Back to top page