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 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 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. 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) 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. 
 
 
 

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

Rogue Wave Software  —  Last change: 02 Apr 1998