Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.

next_permutation- Generates successive permutations of a sequence based on an ordering function.

#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 tooperator< orcomp. 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 returnstrue. If the permutation does not exist, next_permutation returnsfalse, and transforms the permutation into its "first" per- mutation. next_permutation does the transformation according to the lexicographical ordering defined by eitheroperator< (the default used in the first version of the algorithm) orcomp(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 returnsfalse.

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

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

If your compiler does not support default template parame- ters, the you always need to supply theAllocatortemplate 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 forstd.

prev_permutation