next_permutation

Algorithm

• Summary
• Data Type and Member Function Indexes
• Synopsis
• Description
• Complexity
• Example
• Warning
• See Also

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

None

#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);

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 next_permutation algorithm takes a sequence defined by the range [first, last) and transforms it into its next permutation, 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" 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 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.

At most (last - first)/2 swaps are performed.

//
// 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

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

vector<int, allocator<int> >

instead of :

vector<int>

prev_permutation

©Copyright 1996, Rogue Wave Software, Inc.