[ новости /+++ | форум | теги | ]

                       Standard C++ Library
             Copyright 1998, Rogue Wave Software, Inc.


NAME
     prev_permutation

      - Generates 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. For example, if a sequence
     includes the integers 1 2 3, that sequence has six  permuta-
     tions.  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" permu-
     tation. 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)  con-
     tains  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  parame-
     ters,  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

Партнёры:

Хостинг: