名前空間
変種
操作

std::next_permutation

提供: cppreference.com
< cpp‎ | algorithm
 
 
アルゴリズムライブラリ
実行ポリシー (C++17)
非変更シーケンス操作
(C++11)(C++11)(C++11)
(C++17)
変更シーケンス操作
未初期化記憶域の操作
分割操作
ソート操作
(C++11)
二分探索操作
集合操作 (ソート済み範囲用)
ヒープ操作
(C++11)
最小/最大演算
(C++11)
(C++17)
順列
next_permutation
数値演算
C のライブラリ
 
ヘッダ <algorithm> で定義
(1)
template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );
(C++20以前)
template< class BidirIt >
constexpr bool next_permutation( BidirIt first, BidirIt last );
(C++20およびそれ以降)
(2)
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );
(C++20以前)
template< class BidirIt, class Compare >
constexpr bool next_permutation( BidirIt first, BidirIt last, Compare comp );
(C++20およびそれ以降)

範囲 [first, last)operator< または comp について辞書的に順序付けされたすべての順列の集合の次の順列に変換します。 そのような順列が存在すれば true を返し、そうでなければ範囲を (std::sort(first, last) によって行われたかのような) 最初の順列に変換して false を返します。

目次

[編集] 引数

first, last - 置換する要素の範囲
comp - 第1引数が第2引数より小さい場合に true を返す、比較関数オブジェクト (Compare の要件を満たすオブジェクト)。

比較関数のシグネチャは以下と同等であるべきです。

 bool cmp(const Type1 &a, const Type2 &b);

シグネチャが const & を持つ必要はありませんが、関数オブジェクトは渡されたオブジェクトを変更してはなりません。
Type1 および Type2 は、どちらも BidirIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。 ​

型の要件
-
BidirItValueSwappable および BidirectionalIterator の要件を満たさなければなりません。

[編集] 戻り値

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

[編集] 例外

イテレータの操作または要素の swap によって投げられるあらゆる例外。

[編集] 計算量

多くとも N/2 回の swap、ただし N = std::distance(first, last) です。 順列のシーケンス全体を平均すると、一般的な実装では呼び出しあたりおよそ 3 回の比較と 1.5 回の swap を使用します。

[編集] 実装例

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
 
    while (true) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

[編集]

以下のコードは文字列 "aba" の3つの順列をすべて表示します。

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

出力:

aab
aba
baa

[編集] 関連項目

あるシーケンスが別のシーケンスの順列並び替えになっているかどうか調べます
(関数テンプレート) [edit]
指定範囲の要素より辞書的に小さな次の順列を生成します
(関数テンプレート) [edit]