std:: next_permutation

範囲 [ first , last ) を次の 順列 に並べ替えます。そのような「次の順列」が存在する場合は true を返します。それ以外の場合は、範囲を辞書順で最初の順列に変換し（ std::sort によって行われるように）、 false を返します。

* first の型が Swappable でない場合 (C++11以前) BidirIt が ValueSwappable でない場合 (C++11以降) 、動作は未定義です。

パラメータ

戻り値

true 新しい順列が辞書順で前の順列より大きい場合。 false 最後の順列に到達し、範囲が最初の順列にリセットされた場合。

計算量

与えられた \(\scriptsize N\) N を std:: distance ( first, last ) として：

例外

イテレータ操作または要素の交換からスローされる例外。

実装例

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
    auto left = std::is_sorted_until(r_first, r_last);
    if (left != r_last)
    {
        auto right = std::upper_bound(r_first, left, *left);
        std::iter_swap(left, right);
    }
    std::reverse(left.base(), last);
    return left != r_last;
}

`, `$`\; タグ内のテキストは翻訳対象外\; -\; C++固有の用語（関数名、キーワード、型名など）は翻訳せず保持\; 上記のコードブロックは翻訳対象外の要素のみを含んでいるため、日本語への翻訳は行われていません。$

注記

順列の全シーケンスにわたって平均すると、典型的な実装では呼び出しごとに約3回の比較と1.5回のスワップが使用されます。

実装（例： MSVC STL ）は、イテレータ型が LegacyContiguousIterator を満たし、その値型の交換が非自明な特殊メンバ関数も ADL で見つかった swap も呼び出さない場合に、ベクトル化を有効化する可能性があります。

例

#include <algorithm>
#include <iostream>
#include <string>
int main()
{
    std::string s = "aba";
    do
    {
        std::cout << s << '\n';
    }
    while (std::next_permutation(s.begin(), s.end()));
    std::cout << s << '\n';
}

aba
baa
aab

関連項目