random/shuffle.hpp

• View this file on GitHub
• Last update: 2026-08-30 21:41:42+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_bracket.hpp
• random/random_graph.hpp
• setfunc/boolean_range_add_point_get.hpp

Verified with

• test/1_mytest/ancestor_closed_set_knapsack.test.cpp
• test/1_mytest/connected_set_knapsack.test.cpp
• 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/decremental_fastset.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/independent_set_knapsack.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/outer_planar.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/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 1 "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) {
  assert(lim > 0);
  return RNG_64() % lim;
}

ll RNG(ll l, ll r) {
  assert(l < 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