Standard Template Library Programmer's Guide

[2] "Equivalent", not "equal", because two equivalent elements (that is, two elements with the property that neither one is less than the other) are not necessarily equal. Operator< is required to induce a strict weak ordering , not necessarily a total ordering . See the LessThan Comparable requirements for a discussion.

lexicographical_compare , equal , mismatch , search , LessThan Comparable, Strict Weak Ordering, sort

Category: algorithms

Component type: function

Next_permutation is an overloaded name; there are actually two next_permutation functions.

template

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp);

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 .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

For the first version, the one that takes two arguments:

• BidirectionalIterator is a model of Bidirectional Iterator.

• BidirectionalIterator is mutable.

• BidirectionalIterator 's value type is LessThan Comparable.

• The ordering relation on BidirectionalIterator 's value type is a strict weak ordering , as defined in the LessThan Comparable requirements.

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.

• [first, last) is a valid range.

Linear. At most (last – first) / 2 swaps.

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

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(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.

prev_permutation , lexicographical_compare , LessThan Comparable, Strict Weak Ordering, sort

Category: algorithms

Component type: function

Prev_permutation is an overloaded name; there are actually two prev_permutation functions.

template

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp);

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 function object comp .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

For the first version, the one that takes two arguments:

• BidirectionalIterator is a model of Bidirectional Iterator.

• BidirectionalIterator is mutable.

• BidirectionalIterator 's value type is LessThan Comparable.

• The ordering relation on BidirectionalIterator 's value type is a strict weak ordering , as defined in the LessThan Comparable requirements.

For the second version, the one that takes three arguments:

• BidirectionalIterator is a model of Bidirectional Iterator.

• BidirectionalIterator is mutable.