blob: 995bf3a1091935a26b41bcb26ba7b61736970134 [file] [log] [blame]
 next_permutation()
Apache C++ Standard Library Reference Guide

next_permutation()

Library:  Algorithms

Function

Local Index

No Entries

Summary

Algorithm that generates successive permutations of a sequence based on an ordering function

Synopsis

#include <algorithm>

namespace std {
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator start,
BidirectionalIterator finish);

template <class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator start,
BidirectionalIterator finish,
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 the binary predicate 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 [start, finish) 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() transforms the permutation into its "first" permutation and returns false. next_permutation() does the transformation according to the lexicographical ordering defined by either operator<() (used in the first version of the algorithm) or the binary predicate comp (which is user-supplied in the second version of the algorithm).

For example, if the sequence defined by [start, finish) 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 (finish - start)/2 swaps are performed.

Example

//
//  permute.cpp
//

#include <algorithm>  // for next_permutation, prev_permutation
#include <functional> // for less
#include <iostream>   // for cout, endl
#include <numeric>    // for accumulate
#include <vector>     // for vector

int main ()
{
typedef std::vector<int, std::allocator<int> > IntVec;
typedef std::vector<char, std::allocator<char> > CharVec;

// Initialize a vector using an array of integers.
const IntVec::value_type  a1[] = { 0, 0, 0, 0, 1,
0, 0, 0, 0, 0 };
const CharVec::value_type a2[] = "abcdefghji";

// Create the initial set and copies for permuting.
IntVec m1      (a1, a1 + sizeof a1 / sizeof *a1);
IntVec prev_m1 (10);
IntVec next_m1 (10);

CharVec m2      (a2, a2 + sizeof a2 / sizeof *a2 - 1);
CharVec prev_m2 (10);
CharVec next_m2 (10);

std::copy (m1.begin (), m1.end (), prev_m1.begin ());
std::copy (m1.begin (), m1.end (), next_m1.begin ());
std::copy (m2.begin (), m2.end (), prev_m2.begin ());
std::copy (m2.begin (), m2.end (), next_m2.begin ());

// Create permutations.
typedef std::less<IntVec::value_type>  IntLess;
typedef std::less<CharVec::value_type> CharLess;

std::prev_permutation (prev_m1.begin (), prev_m1.end (),
IntLess ());
std::next_permutation (next_m1.begin (), next_m1.end (),
IntLess ());
std::prev_permutation (prev_m2.begin (), prev_m2.end (),
CharLess ());
std::next_permutation (next_m2.begin (), next_m2.end (),
CharLess ());

// Output results.

typedef std::ostream_iterator<IntVec::value_type, char,
std::char_traits<char> >
IntOSIter;

typedef std::ostream_iterator<CharVec::value_type, char,
std::char_traits<char> >
CharOSIter;

std::cout << "Example 1: \n     Original values:      ";
std::copy (m1.begin (), m1.end (),
IntOSIter (std::cout, " "));

std::cout << "\n     Previous permutation: ";
std::copy (prev_m1.begin (), prev_m1.end (),
IntOSIter (std::cout, " "));

std::cout << "\n     Next Permutation:     ";
std::copy (next_m1.begin (), next_m1.end (),
IntOSIter (std::cout, " "));

std::cout << "\n\nExample 2: \n     ";
<< "Original values:      ";
std::copy (m2.begin (), m2.end (),
CharOSIter (std::cout, " "));

std::cout << "\n     Previous Permutation: ";
std::copy (prev_m2.begin (), prev_m2.end (),
CharOSIter (std::cout, " "));

std::cout << "\n     Next Permutation:     ";
std::copy (next_m2.begin (), next_m2.end (),
CharOSIter (std::cout, " "));

std::cout << std::endl << std::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