next_permutation (3C++std) - Tru64 UNIX
Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc. NAME
next_permutation - Generate 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. So, for example, if a sequence includes the integers 1 2 3, that
sequence has six permutations, which, in order from first to last 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
(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.h>
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;
}
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
WARNING
If your compiler does not support default template parameters, the you need
to always supply the Allocator template argument. For instance, you will
need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
prev_permutation
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
|