std::prev_permutation
| ヘッダ <algorithm>
|
||
template< class BidirIt >
bool prev_permutation( BidirIt first, BidirIt last );
|
で定義 (1) | (C++20 から constexpr) |
template< class BidirIt, class Compare >
bool prev_permutation( BidirIt first, BidirIt last, Compare comp );
|
(2) | (C++20 から constexpr) |
範囲 [first, last) を前の 順列に変換します。そのような順列が存在する場合は true を返し、それ以外の場合は範囲を最後の順列 (降順) に変換して false を返します。
operator<(C++20 まで)std::less{}(C++20 から) に関して辞書順に並べられます。comp に関して辞書順に並べられます。の型が *first の (C++11 まで)Swappable ではなく (C++11 から)BidirItValueSwappable ではない場合、動作は未定義です。
目次
first, last
| - | 順列を生成する | 範囲 を定義するイテレータのペア comp |
| - | 比較関数オブジェクト ( | Compare の要件を満たすオブジェクト)。第一引数が第二引数より小さいtrue場合に を返します。比較関数のシグネチャは以下と同等であるべきです:
シグネチャに
が含まれている必要はありませんが、関数は渡されたオブジェクトを変更してはならず、型 (const の可能性がある) |
| - | ||
は BidirItValueSwappable と LegacyBidirectionalIterator の要件を満たさなければなりません。
戻り値 | ||
新しい順列が辞書順で古い順列より前にある場合、
true 。最初の順列に達し、範囲が最後の順列にリセットされた場合、false 。
例外
イテレータ操作または要素のスワップから投げられる例外。
計算量
N を std::distance(first, last) とすると:
| N |
| 2 |
実装例
template<class BidirIt>
bool prev_permutation(BidirIt first, BidirIt last)
{
if (first == last)
return false;
BidirIt i = last;
if (first == --i)
return false;
while (1)
{
BidirIt i1, i2;
i1 = i;
if (*i1 < *--i)
{
i2 = last;
while (!(*--i2 < *i))
;
std::iter_swap(i, i2);
std::reverse(i1, last);
return true;
}
if (i == first)
{
std::reverse(first, last);
return false;
}
}
}
|
注記
順列の全シーケンスで平均すると、一般的な実装は呼び出しあたり約3回の比較と1.5回のスワップを行います。
実装 (例: MSVC STL) は、イテレータ型が LegacyContiguousIterator を満たし、その値型のスワップが非トリビアルな特殊メンバ関数や ADL により見つかる swap を呼び出さない場合にベクトル化を有効にすることがあります。
例
以下のコードは、文字列 "cab" の6つの順列をすべて逆順に出力します。
#include <algorithm>
#include <iostream>
#include <string>
int main()
{
std::string s = "cab";
do
{
std::cout << s << ' ';
}
while (std::prev_permutation(s.begin(), s.end()));
std::cout << s << '\n';
}
出力:
cab bca bac acb abc cba
関連項目
(C++11) |
シーケンスが別のシーケンスの順列であるかどうかを判定します (関数テンプレート & アルゴリズム関数オブジェクト) |
(C++20) |
|
| 範囲の要素の次の辞書順に大きな順列を生成します (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
(C++20) |
範囲の要素の次の辞書順に小さい順列を生成します (アルゴリズム関数オブジェクト) |