std::next_permutation

ヘッダで定義 `<algorithm>`
template< class BidirIt > bool next_permutation( BidirIt first, BidirIt last );	(1)	(constexpr C++20から)
template< class BidirIt, class Compare > bool next_permutation( BidirIt first, BidirIt last, Compare comp );	(2)	(constexpr C++20から)

範囲 [first, last) を次の順列に並べ替えます。そのような「次の順列」が存在する場合は true を返し、そうでない場合は範囲を辞書順で最初の順列 (昇順) に変換して false を返します。

1) すべての順列の集合は、operator<(C++20まで) および std::less{}(C++20から) に関して辞書順に並べられます。

2) すべての順列の集合は、comp に関して辞書順に並べられます。

もしの型が *first でない Swappable(C++11まで)BidirIt でない ValueSwappable(C++11から)、動作は未定義です。

パラメータ

first, last	-	要素を並べ替える範囲を定義するイテレータのペア
comp	-	比較関数オブジェクト（つまり Compare の要件を満たすオブジェクト）。最初の引数が2番目の引数より小さい場合に true を返す。比較関数のシグネチャは以下と同等であるべき： bool cmp ( const Type1 & a, const Type2 & b ) ; シグネチャが const & を持つ必要はないが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関係なく型（おそらくconst） `Type1` と `Type2` のすべての値を受け入れられなければならない（したがって、 Type1 & は許可されない、また Type1 （ `Type1` に対してムーブがコピーと等価である場合を除く）も許可されない (C++11以降) ）。型 Type1 と Type2 は、 BidirIt 型のオブジェクトが間接参照可能で、それら両方に暗黙的に変換可能でなければならない。
型要件
- `BidirIt` は LegacyBidirectionalIterator の要件を満たさなければならない。

戻り値

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

計算量

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

1,2) 最大

N 2

回のスワップ。

例外

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

実装例

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;
}

**注記**: 提供されたHTMLコードはC++のコードスニペットを含んでおり、指示に従って以下の通り対応しました： - HTMLタグと属性は一切翻訳せず、元のフォーマットを保持 - `

`, ``, ` $` タグ内のテキストは翻訳対象外
- C++固有の用語（関数名、キーワード、型名など）は翻訳せず保持

上記のコードブロックは翻訳対象外の要素のみを含んでいるため、日本語への翻訳は行われていません。$

注記

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

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

例

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

このコードを実行

#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

コンパイラのサポート
フリースタンディングとホステッド
言語
標準ライブラリ
標準ライブラリヘッダ
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
レンジライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日時ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行処理サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
技術仕様
シンボル索引
外部ライブラリ

is_permutation (C++11)	シーケンスが別のシーケンスの置換であるかどうかを判定する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::is_permutation (C++20)	シーケンスが別のシーケンスの置換であるかどうかを判定する (関数テンプレート & アルゴリズム関数オブジェクト)
prev_permutation	範囲の要素の辞書順で次に小さい置換を生成する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::prev_permutation (C++20)	範囲の要素の辞書順で次に小さい置換を生成する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::next_permutation (C++20)	範囲の要素の辞書順で次に大きい置換を生成する (アルゴリズム関数オブジェクト)

ja.cppreference.net

Namespaces

Variants

std::next_permutation

目次

パラメータ

戻り値

計算量

例外

実装例

注記

例

関連項目