std::prev_permutation
Defined in header
<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) | |
Transforms the range [first, last)
into the previous permutation from the set of all permutations that are lexicographically ordered with respect to operator<
or comp
. Returns true if such permutation exists, otherwise transforms the range into the last permutation (as if by std::sort(first, last); std::reverse(first, last);
) and returns false.
Contents |
[edit] Parameters
first, last | - | the range of elements to permute |
comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare ) which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function object must not modify the objects passed to it. |
Type requirements | ||
-
BidirIt must meet the requirements of ValueSwappable and BidirectionalIterator .
|
[edit] Return value
true if the new permutation precedes the old in lexicographical order. false if the first permutation was reached and the range was reset to the last permutation.
[edit] Exceptions
Any exceptions thrown from iterator operations or the element swap.
[edit] Complexity
At most (last-first)/2
swaps.
[edit] Possible implementation
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; } } } |
[edit] Example
The following code prints all six permutations of the string "abc" in reverse order
#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'; }
Output:
cba cab bca bac acb abc
[edit] See also
(C++11)
|
determines if a sequence is a permutation of another sequence (function template) |
prev_permutation |
generates the next smaller lexicographic permutation of a range of elements (function template) |