Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library Reference Guide

next_permutation()

Library:  Algorithms


Function

Local Index

No Entries

Summary

Algorithm that generates successive permutations of a sequence based on an ordering function

Synopsis

#include <algorithm>

namespace std {
  template <class BidirectionalIterator>
  bool next_permutation(BidirectionalIterator start,
                        BidirectionalIterator finish);

 template <class BidirectionalIterator, class Compare>
  bool next_permutation(BidirectionalIterator start,
                        BidirectionalIterator finish,
                        Compare comp);
}

Description

The permutation-generating algorithms, next_permutation() and prev_permutation(), assume that the set of all permutations of the elements in a sequence is lexicographically sorted with respect to operator<() or the binary predicate comp. For example, if a sequence includes the integers 1 2 3, that sequence has six permutations. In order from first to last, they are: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, and 3 2 1.

The next_permutation() algorithm takes a sequence defined by the range [start, finish) and transforms it into its next permutation, if possible. If such a permutation does exist, the algorithm completes the transformation and returns true. If the permutation does not exist, next_permutation() transforms the permutation into its "first" permutation and returns false. next_permutation() does the transformation according to the lexicographical ordering defined by either operator<() (used in the first version of the algorithm) or the binary predicate comp (which is user-supplied in the second version of the algorithm).

For example, if the sequence defined by [start, finish) contains the integers 3 2 1 (in that order), there is not a "next permutation." Therefore, the algorithm transforms the sequence into its first permutation (1 2 3) and returns false.

Complexity

At most (finish - start)/2 swaps are performed.

Example

See Also

prev_permutation()

Standards Conformance

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.9



Previous fileTop of DocumentContentsIndex pageNext file