最終更新日時(UTC):
が更新

履歴 編集

function template
<algorithm>

std::ranges::shuffle(C++20)

namespace std::ranges {
  // (1)
  template<random_access_iterator I, sentinel_for<I> S, class Gen>
    requires permutable<I> && uniform_random_bit_generator<remove_reference_t<Gen>>
  I shuffle(I first, S last, Gen&& g);

  // (2)
  template<random_access_range R, class Gen>
    requires permutable<iterator_t<R>> && uniform_random_bit_generator<remove_reference_t<Gen>>
  borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);
}

概要

[first,last) のそれぞれの要素を同じ確率で並び替える。

  • (1): イテレータペアで範囲を指定する
  • (2): 範囲を直接指定する

計算量

正確に (last - first) - 1 回 swap する。

備考

以下の実装では、フィッシャー - イェーツのシャッフルアルゴリズムが使用されている:

  • GCC: 4.9 (libstdc++)
  • Clang: 3.4 (libc++)
  • Visual C++: 2013

整数の配列をシャッフルする

#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <iterator>
#include <random>

int main() {
  std::vector<int> v(10);
  std::iota(v.begin(), v.end(), 0); // 0~9 までの値を生成

  std::cout << "before: ";
  std::ranges::copy(v, std::ostream_iterator<int>(std::cout));
  std::cout << std::endl;

  // シャッフル
  std::random_device seed_gen;
  std::mt19937 engine(seed_gen());
  std::ranges::shuffle(v, engine);

  std::cout << " after: ";
  std::ranges::copy(v, std::ostream_iterator<int>(std::cout));
  std::cout << std::endl;
}

出力例

before: 0123456789
 after: 5803429716

文字列をシャッフルする

#include <algorithm>
#include <iostream>
#include <string>
#include <random>

int main() {
  std::string input = "0123456789abcdef";

  std::cout << "before: " << input << std::endl;

  // シャッフル
  std::random_device seed_gen;
  std::mt19937 engine(seed_gen());
  std::ranges::shuffle(input, engine);

  std::cout << " after: " << input << std::endl;
}

出力例

before: 0123456789abcdef
 after: 49e351b8f0ad62c7

バージョン

言語

  • C++20

処理系

参照