4. shuffle

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

履歴 編集

function template
<algorithm>

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

namespace std::ranges {
  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); // (1) C++20

  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); // (2) C++20
}

概要

範囲のそれぞれの要素を同じ確率で並び替える。

計算量

正確に (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

処理系

参照