名前空間
変種
操作

std::random_shuffle, std::shuffle

提供: cppreference.com
< cpp‎ | algorithm
 
 
アルゴリズムライブラリ
実行ポリシー (C++17)
非変更シーケンス操作
(C++11)(C++11)(C++11)
(C++17)
変更シーケンス操作
random_shuffle
(C++17以前)

未初期化記憶域の操作
分割操作
ソート操作
(C++11)
二分探索操作
集合操作 (ソート済み範囲用)
ヒープ操作
(C++11)
最小/最大演算
(C++11)
(C++17)
順列
数値演算
C のライブラリ
 
ヘッダ <algorithm> で定義
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );
(1) (C++14で非推奨)
(C++17で削除)
(2)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );
(C++11以前)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );
(C++11およびそれ以降)
(C++14で非推奨)
(C++17で削除)
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
(3) (C++11およびそれ以降)

指定された範囲 [first, last) の要素を、それらの有り得る順列それぞれが等しい出現率を持つように、並び替えます。

1) 乱数ジェネレータは処理系定義ですが、関数 std::rand がしばしば使用されます。
2) 乱数ジェネレータは関数オブジェクト r です。
3) 乱数ジェネレータは関数オブジェクト g です。

目次

[編集] 引数

first, last - ランダムにシャッフルする要素の範囲
r - r(n) のように呼ばれた場合に区間 [0,n) 内の std::iterator_traits<RandomIt>::difference_type に変換可能な型のランダムに選択された値を返す関数オブジェクト
g - 結果の型が std::iterator_traits<RandomIt>::difference_type に変換可能な UniformRandomBitGenerator
型の要件
-
RandomItValueSwappable および RandomAccessIterator の要件を満たさなければなりません。
-
std::remove_reference_t<URBG>UniformRandomBitGenerator の要件を満たさなければなりません。

[編集] 戻り値

(なし)

[編集] 計算量

firstlast の距離に比例。

[編集] ノート

実装は標準によって規定されていないため、まったく同じ RandomFuncURBG を使用したとしても、異なる標準ライブラリ実装では異なる結果が得られる可能性があります。

[編集] 実装例

1つめのバージョン
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last )
{
    typename std::iterator_traits<RandomIt>::difference_type i, n;
    n = last - first;
    for (i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i], first[std::rand() % (i+1)]);
        // rand() % (i+1) isn't actually correct, because the generated number
        // is not uniformly distributed for most values of i. A correct implementation
        // will need to essentially reimplement C++11 std::uniform_int_distribution,
        // which is beyond the scope of this example.
    }
}
2つめのバージョン
template<class RandomIt, class RandomFunc>
void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r)
{
    typename std::iterator_traits<RandomIt>::difference_type i, n;
    n = last - first;
    for (i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i], first[r(i+1)]);
    }
}
3つめのバージョン
template<class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
    typedef std::uniform_int_distribution<diff_t> distr_t;
    typedef typename distr_t::param_type param_t;
 
    distr_t D;
    diff_t n = last - first;
    for (diff_t i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);
    }
}

[編集]

以下のコードは 1〜10 の整数をランダムにシャッフルします。

#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>
 
int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
    std::random_device rd;
    std::mt19937 g(rd());
 
    std::shuffle(v.begin(), v.end(), g);
 
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

出力例:

8 6 10 4 2 3 7 1 9 5

[編集] 関連項目

指定範囲の要素より辞書的に大きな次の順列を生成します
(関数テンプレート) [edit]
指定範囲の要素より辞書的に小さな次の順列を生成します
(関数テンプレート) [edit]