Category: algorithms | Component type: function |
template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); template <class BidirectionalIterator, class StrictWeakOrdering> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp);
The postcondition is that the new permutation of elements is lexicographically greater than the old (as determined by lexicographical_compare) if and only if the return value is true.
The two versions of next_permutation differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
template <class BidirectionalIterator> void snail_sort(BidirectionalIterator first, BidirectionalIterator last) { while (next_permutation(first, last)) {} } int main() { int A[] = {8, 3, 6, 1, 2, 5, 7, 4}; const int N = sizeof(A) / sizeof(int); snail_sort(A, A+N); copy(A, A+N, ostream_iterator<int>(cout, "\n")); }
[1] If all of the elements in [first, last) are distinct from each other, then there are exactly N! permutations. If some elements are the same as each other, though, then there are fewer. There are, for example, only three (3!/2!) permutations of the elements 1 1 2.
[2] Note that the lexicographically smallest permutation is, by definition, sorted in nondecreasing order.
Contact Us | Site Map | Trademarks | Privacy | Using this site means you accept its Terms of Use |
Copyright © 2009 - 2017 Silicon Graphics International. All rights reserved. |