Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  prev_permutation  - Generate successive permutations of a sequence based on
  an ordering function.

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.  So, for example, if a sequence includes the integers 1 2 3, that
  sequence has six permutations, which, in order from first to last, 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 (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.h>

  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;
   }

  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

WARNING

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

  vector<int, allocator<int> >

  instead of :

  vector<int>

SEE ALSO

  next_permutation

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement