std::random_shuffle, std::shuffle

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );

template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

指定範囲 [first, last) の要素を並べ替え、各順列が等確率で出現するようにします。

*firstの型が Swappable ではない (C++11まで)RandomItValueSwappable ではない (C++11から) 場合、動作は未定義です。

パラメータ

計算量

正確に std:: distance ( first, last ) - 1 回のスワップ。

実装例

実装例については libstdc++ および libc++ も参照してください。

template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[std::rand() % (i + 1)]);
        // rand() % (i + 1) は実際には正しくありません。なぜなら、生成される数値が
        // ほとんどの i の値に対して均一に分布しないためです。正しいコードは
        // C++11 std::uniform_int_distribution 実装のバリエーションになります。
    }
}

template<class RandomIt, class RandomFunc>
void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[r(i + 1)]);
    }
}

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;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);
    }
}

注記

実装は標準で規定されていないため、たとえ同じ RandomFunc または URBG （一様乱数生成器）を使用した場合でも、標準ライブラリの実装が異なれば結果が異なる可能性があることに注意してください。

C++17でstd::random_shuffleが削除された理由は、イテレータのみのバージョンが通常std::randに依存しているためです。std::randは非推奨の検討がなされています（std::randは有害と見なされているため、<random>ヘッダーのクラスで置き換えるべきです）。さらに、イテレータのみのstd::random_shuffleバージョンは通常、グローバル状態に依存します。std::shuffleのシャッフルアルゴリズムは、第3引数としてURBGを使用するため、推奨される代替手段です。

例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
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

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

1. ↑ オーバーロード (3) も同じ欠陥を持っていますが、その解決策の一部はC++98には適用されません。

関連項目