 

Category: algorithms   Component type: function 
Prototype
Prev_permutation
is an overloaded name; there are actually two prev_permutation
functions.
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template <class BidirectionalIterator, class StrictWeakOrdering>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last,
StrictWeakOrdering comp);
Description
Prev_permutation
transforms the range of elements [first, last)
into the lexicographically next smaller 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 previous. If such a permutation exists, prev_permutation
transforms [first, last)
into that permutation and returns true
. Otherwise it transforms [first, last)
into the lexicographically greatest permutation [2] and returns false
.
The postcondition is that the new permutation of elements is lexicographically less than the old (as determined by lexicographical_compare
) if and only if the return value is true
.
The two versions of prev_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 functors comp
.
Definition
Defined in the standard header algorithm, and in the nonstandard backwardcompatibility header algo.h.
Requirements on types
For the first version:

BidirectionalIterator
is a model of BidirectionalIterator.

BidirectionalIterator
is mutable.

BidirectionalIterator
's value type is LessThanComparable.

The ordering relation on
BidirectionalIterator
's value type is a strict weak ordering, as defined in the LessThanComparable requirements.
For the second version:

BidirectionalIterator
is a model of BidirectionalIterator.

BidirectionalIterator
is mutable.

StrictWeakOrdering
is a model of StrictWeakOrdering.

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
int main()
{
int A[] = {2, 3, 4, 5, 6, 1};
const int N = sizeof(A) / sizeof(int);
cout << "Initially: ";
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
prev_permutation(A, A+N);
cout << "After prev_permutation: ";
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
next_permutation(A, A+N);
cout << "After next_permutation: ";
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout << endl;
}
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 greatest permutation is, by definition, sorted in nonascending order.
See also
next_permutation
, lexicographical_compare
, LessThanComparable, StrictWeakOrdering, sort