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

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


NAME
     next_permutation

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



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

     template <class BidirectionalIterator, class Compare>
     bool next_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 next_permutation algorithm takes a sequence  defined  by
     the range [first, last) and transforms it into its next per-
     mutation, if possible. If such a permutation does exist, the
     algorithm  completes the transformation and returns true. If
     the permutation does  not  exist,  next_permutation  returns
     false,  and transforms the permutation into its "first" per-
     mutation. next_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  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 (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,  the  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
     prev_permutation

Партнёры:

Хостинг: