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

prev_permutation()

Library:  Algorithms


Function

Local Index

No Entries

Summary

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

Synopsis

#include <algorithm>

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

  template <class BidirectionalIterator, class Compare>
  bool prev_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 prev_permutation() algorithm takes a sequence defined by the range [start, finish) and transforms it into its previous permutation, if possible. If such a permutation does exist, the algorithm completes the transformation and returns true. If the permutation does not exist, prev_permutation() returns false, and transforms the permutation into its last permutation. prev_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 1 2 3 (in that order), there is not a previous permutation. Therefore, the algorithm transforms the sequence into its last permutation (3 2 1) and returns false.

Complexity

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

Example

See Also

next_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