next_permutation


Category: algorithms 
Component type: function 
Prototype
Next_permutation is an overloaded name; there are actually two next_permutation
functions.
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
StrictWeakOrdering comp);
Description
Next_permutation transforms the range of elements [first, last)
into the lexicographically next greater permutation of the elements.
There is a finite number of distinct permutations (at most
N! [1], where N is last  first), so, if the permutations are
ordered by lexicographical_compare, there is an unambiguous
definition of which permutation is lexicographically next. If such
a permutation exists, next_permutation transforms [first, last)
into that permutation and returns true. Otherwise it transforms
[first, last) into the lexicographically smallest permutation [2]
and returns false.
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.
Definition
Defined in the standard header algorithm, and in the nonstandard
backwardcompatibility header algo.h.
Requirements on types
For the first version, the one that takes two arguments:
For the second version, the one that takes three arguments:

BidirectionalIterator is a model of Bidirectional Iterator.

BidirectionalIterator is mutable.

StrictWeakOrdering is a model of Strict Weak Ordering.

BidirectionalIterator's value type is convertible to
StrictWeakOrdering's argument type.
Preconditions

[first, last) is a valid range.
Complexity
Linear. At most (last  first) / 2 swaps.
Example
This example uses next_permutation to implement the worst known
deterministic sorting algorithm. Most sorting algorithms are
O(N log(N)), and even bubble sort is only
O(N^2). This algorithm is actually O(N!).
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"));
}
Notes
[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.
See also
prev_permutation, lexicographical_compare,
LessThan Comparable, Strict Weak Ordering, sort
Copyright ©
1999 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation
webmaster@www.sgi.com