std::next_permutation
Defined in header
<algorithm>
|
||
template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last ); |
(1) | |
template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp ); |
(2) | |
Transforms the range [first, last)
into the next 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 first permutation (as if by std::sort(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 is lexicographically greater than the old. false if the last permutation was reached and the range was reset to the first permutation.
[edit] Exceptions
Any exceptions thrown from iterator operations or the element swap.
[edit] Complexity
At most N/2 swaps, where N = std::distance(first, last).
[edit] Possible implementation
template<class BidirIt> bool next_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 (*--i < *i1) { i2 = last; while (!(*i < *--i2)) ; 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 three permutations of the string "aba"
#include <algorithm> #include <string> #include <iostream> int main() { std::string s = "aba"; std::sort(s.begin(), s.end()); do { std::cout << s << '\n'; } while(std::next_permutation(s.begin(), s.end())); }
Output:
aab aba baa
[edit] See also
(C++11)
|
determines if a sequence is a permutation of another sequence (function template) |
generates the next smaller lexicographic permutation of a range of elements (function template) |