# Man Page next_permutation.3

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

vector<int>

If your compiler does not support namespaces,  then  you  do
not need the using declaration for std.

```

```     prev_permutation

```