namespace std {
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last); // (1) C++03
template <class BidirectionalIterator>
constexpr bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last); // (1) C++20
template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Compare comp); // (2) C++03
template <class BidirectionalIterator, class Compare>
constexpr bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Compare comp); // (2) C++20
}
概要
前の順列を生成する。
要件
BidriectionalIteratorがValueSwappableの要件を満たしていること。
効果
イテレータ範囲[first, last)を前の順列に変換する。
operator<またはcompによって辞書順に並んでいる全ての順列の集合があると仮定すると、前の順列が発見される。
戻り値
前の順列が存在する場合はtrueを返し、そうでなければfalseを返す。
計算量
高々(last - first)/2回の要素の交換
備考
全ての順列を取得したい場合は、この関数に最初に与えるイテレータ範囲が、降順にソート済みになっていること。
例
#include <iostream>
#include <vector>
#include <algorithm>
void print(const std::vector<int>& v)
{
std::for_each(v.begin(), v.end(), [](int x) {
std::cout << x << " ";
});
std::cout << std::endl;
}
int main ()
{
// 降順にソート済みの入力
std::vector<int> v = {3, 2, 1};
do {
print(v);
} while (std::prev_permutation(v.begin(), v.end()));
}
出力
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3
実装例
template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
if (first == last)
return false;
BidirectionalIterator i = first;
++i;
if (i == last)
return false;
i = last;
--i;
for(;;) {
BidirectionalIterator ii = i;
--i;
if (comp(*ii, *i)) {
BidirectionalIterator j = last;
while (!comp(*--j, *i)) {}
std::swap(*i, *j);
std::reverse(ii, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
using value_type = typename std::iterator_traits<BidirectionalIterator>::value_type;
return prev_permutation(first, last, std::less<value_type>());
}