std::prev_permutation
提供: cppreference.com
ヘッダ <algorithm> で定義 | ||
template<class BidirIt > bool prev_permutation( BidirIt first, BidirIt last); | (1) | |
template<class BidirIt, class Compare > bool prev_permutation( BidirIt first, BidirIt last, Compare comp); | (2) | |
範囲 [first, last) を operator< または comp について辞書的に順序付けされたすべての順列の集合の前の順列に変換します。 そのような順列が存在すれば true を返し、そうでなければ範囲を (std::sort(first, last); std::reverse(first, last); によって行われたかのような) 最後の順列に変換して false を返します。
目次 |
[編集]引数
| first, last | - | 置換する要素の範囲 |
| comp | - | 第1引数が第2引数より小さい場合に true を返す、比較関数オブジェクト (Compare の要件を満たすオブジェクト)。比較関数のシグネチャは以下と同等であるべきです。 bool cmp(const Type1 &a, const Type2 &b); シグネチャが const& を持つ必要はありませんが、関数オブジェクトは渡されたオブジェクトを変更してはなりません。 |
| 型の要件 | ||
-BidirIt は ValueSwappable および BidirectionalIterator の要件を満たさなければなりません。 | ||
[編集]戻り値
新しい順列が古い順列より辞書順で前に来る場合は true。 最初の順列に達して範囲が最後の順列にリセットされた場合は false。
[編集]例外
イテレータの操作または要素の swap によって投げられるあらゆる例外。
[編集]計算量
多くとも (last-first)/2 回の swap。 順列のシーケンス全体を平均すると、一般的な実装では呼び出しあたりおよそ 3 回の比較と 1.5 回の swap を使用します。
[編集]実装例
template<class BidirIt>bool prev_permutation(BidirIt first, BidirIt last){if(first == last)returnfalse; BidirIt i = last;if(first ==--i)returnfalse; while(1){ BidirIt i1, i2; i1 = i;if(*i1 <*--i){ i2 = last;while(!(*--i2 <*i));std::iter_swap(i, i2);std::reverse(i1, last);returntrue;}if(i == first){std::reverse(first, last);returnfalse;}}} |
[編集]例
以下のコードは文字列 "abc" の6つの順列すべてを逆順に表示します。
Run this code
#include <algorithm>#include <string>#include <iostream>#include <functional>int main(){std::string s="abc";std::sort(s.begin(), s.end(), std::greater<char>());do{std::cout<< s <<' ';}while(std::prev_permutation(s.begin(), s.end()));std::cout<<'\n';}
出力:
cba cab bca bac acb abc
[編集]関連項目
(C++11) | あるシーケンスが別のシーケンスの順列並び替えになっているかどうか調べます (関数テンプレート) |
| 指定範囲の要素より辞書的に大きな次の順列を生成します (関数テンプレート) |
