Module: Standard C++ Library Library: Algorithms
Function
Algorithm that generates successive permutations of a sequence based on an ordering function
#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);
}
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.
At most (finish - start)/2 swaps are performed.
//
// 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
ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.9
Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).