## prev_permutation

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

Generates successive permutations of a sequence based on an ordering function.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### Synopsis

    #include <algorithm>
    template <class BidirectionalIterator>
    bool prev_permutation (BidirectionalIterator first,
                           BidirectionalIterator last);

    template <class BidirectionalIterator, class Compare>
    bool prev_permutation (BidirectionalIterator first,
                           BidirectionalIterator last,
                           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 `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 `[first, last)` 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<` (the default used in the first version of the algorithm) or `comp` (which is user-supplied in the second version of the algorithm).

For example, if the sequence defined by `[first, last)` 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 `(last - first)/2` swaps are performed.

### Example

    //
    // permute.cpp
    //
     #include <numeric>    //for accumulate
     #include <vector>        //for vector
     #include <functional> //for less
     #include <iostream>
     using namespace std;

     int main()
     {
       //Initialize a vector using an array of ints
       int  a1[] = {0,0,0,0,1,0,0,0,0,0};
       char a2[] = "abcdefghji";

       //Create the initial set and copies for permuting
       vector<int>  m1(a1, a1+10);
       vector<int>  prev_m1((size_t)10), next_m1((size_t)10);
       vector<char> m2(a2, a2+10);
       vector<char> prev_m2((size_t)10), next_m2((size_t)10);

       copy(m1.begin(), m1.end(), prev_m1.begin());
       copy(m1.begin(), m1.end(), next_m1.begin());
       copy(m2.begin(), m2.end(), prev_m2.begin());
       copy(m2.begin(), m2.end(), next_m2.begin());

       //Create permutations
       prev_permutation(prev_m1.begin(),
                        prev_m1.end(),less<int>());
       next_permutation(next_m1.begin(),
                        next_m1.end(),less<int>());
       prev_permutation(prev_m2.begin(),
                        prev_m2.end(),less<int>());
       next_permutation(next_m2.begin(),
                        next_m2.end(),less<int>());
       //Output results
       cout << "Example 1: " << endl << "     ";
       cout << "Original values:      ";
       copy(m1.begin(),m1.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl << "     ";
       cout << "Previous permutation: ";
       copy(prev_m1.begin(),prev_m1.end(),
            ostream_iterator<int,char>(cout," "));

       cout << endl<< "     ";
       cout << "Next Permutation:     ";
       copy(next_m1.begin(),next_m1.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl << endl;

       cout << "Example 2: " << endl << "     ";
       cout << "Original values: ";
       copy(m2.begin(),m2.end(),
            ostream_iterator<char,char>(cout," "));
       cout << endl << "     ";
       cout << "Previous Permutation: ";
       copy(prev_m2.begin(),prev_m2.end(),
            ostream_iterator<char,char>(cout," "));
       cout << endl << "     ";

       cout << "Next Permutation:     ";
       copy(next_m2.begin(),next_m2.end(),
            ostream_iterator<char,char>(cout," "));
       cout << endl << endl;

       return 0;
     }

Program Output

    Example 1:
         Original values:      0 0 0 0 1 0 0 0 0 0
         Previous permutation: 0 0 0 0 0 1 0 0 0 0
         Next Permutation:     0 0 0 1 0 0 0 0 0 0
    Example 2:
         Original values: a b c d e f g h j i
         Previous Permutation: a b c d e f g h i j
         Next Permutation:     a b c d e f g i h j

### Warnings

If your compiler does not support default template parameters, then you always need to supply the `Allocator` template argument. For instance, you need to write:

`vector<int, allocator<int> >`

instead of:

`vector<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

### See Also

next_permutation

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998