.\" ident @(#)prev_permutation.3 .\" Standard Template Library .\" $$RW_INSERT_HEADER "slyrs.man" .TH prev_permutation 3C++ "02 Apr 1998" "Rogue Wave Software" "-" .ce2 Standard C++ Library Copyright 1998, Rogue Wave Software, Inc. .SH NAME \f2prev_permutation\fP \ - Generates successive permutations of a sequence based on an ordering function. .SH SYNOPSIS .br #include .br template .br bool prev_permutation (BidirectionalIterator first, .RE .RS 22 BidirectionalIterator last); .RE .RS 0 .br template .br bool prev_permutation (BidirectionalIterator first, .RE .RS 22 BidirectionalIterator last, .br Compare comp); .SH 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 \f2operator<\fP or \f2comp\fP. 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 prev_permutation algorithm takes a sequence defined by the range \f2[first, last)\fP and transforms it into its previous permutation, if possible. If such a permutation does exist, the algorithm completes the transformation and returns \f2true\fP. If the permutation does not exist, prev_permutation returns \f2false\fP, and transforms the permutation into its "last" permutation. prev_permutation does the transformation according to the lexicographical ordering defined by either \f2operator<\fP (the default used in the first version of the algorithm) or \f2comp\fP (which is user-supplied in the second version of the algorithm). For example, if the sequence defined by \f2[first, last)\fP contains the integers 1 2 3 (in that order), there is not a "previous permutation." Therefore, the algorithm transforms the sequence into its last permutation (3 2 1) and returns \f2false\fP. .SH COMPLEXITY At most\f2 (last - first)/2 \fPswaps are performed. .SH EXAMPLE .RE .RS 0 // .br // permute.cpp .br // .RE .RS 1 #include //for accumulate .br #include //for vector .br #include //for less .br #include .RE .RS 0 using namespace std; .br .br int main() .RE .RS 1 { .RE .RS 3 //Initialize a vector using an array of ints .RE .RS 2 int a1[] = {0,0,0,0,1,0,0,0,0,0}; .br char a2[] = "abcdefghji"; .RE .RS 0 .RE .RS 3 //Create the initial set and copies for permuting .RE .RS 2 vector m1(a1, a1+10); .br vector prev_m1((size_t)10), next_m1((size_t)10); .br vector m2(a2, a2+10); .br vector prev_m2((size_t)10), next_m2((size_t)10); .RE .RS 0 .RE .RS 2 copy(m1.begin(), m1.end(), prev_m1.begin()); .br copy(m1.begin(), m1.end(), next_m1.begin()); .br copy(m2.begin(), m2.end(), prev_m2.begin()); .br copy(m2.begin(), m2.end(), next_m2.begin()); .RE .RS 0 .RE .RS 3 //Create permutations .RE .RS 2 prev_permutation(prev_m1.begin(), .RE .RS 19 prev_m1.end(),less()); .RE .RS 2 next_permutation(next_m1.begin(), .RE .RS 19 next_m1.end(),less()); .RE .RS 1 prev_permutation(prev_m2.begin(), .RE .RS 19 prev_m2.end(),less()); .RE .RS 2 next_permutation(next_m2.begin(), .RE .RS 19 next_m2.end(),less()); .RE .RS 3 //Output results .RE .RS 2 cout << "Example 1: " << endl << " "; .br cout << "Original values: "; .br copy(m1.begin(),m1.end(), .RE .RS 7 ostream_iterator(cout," ")); .RE .RS 2 cout << endl << " "; .br cout << "Previous permutation: "; .br copy(prev_m1.begin(),prev_m1.end(), .RE .RS 7 ostream_iterator(cout," ")); .RE .RS 0 .RE .RS 2 cout << endl<< " "; .br cout << "Next Permutation: "; .br copy(next_m1.begin(),next_m1.end(), .RE .RS 7 ostream_iterator(cout," ")); .RE .RS 2 cout << endl << endl; .RE .RS 0 .RE .RS 2 cout << "Example 2: " << endl << " "; .br cout << "Original values: "; .br copy(m2.begin(),m2.end(), .RE .RS 7 ostream_iterator(cout," ")); .RE .RS 2 cout << endl << " "; .br cout << "Previous Permutation: "; .br copy(prev_m2.begin(),prev_m2.end(), .RE .RS 7 ostream_iterator(cout," ")); .RE .RS 2 cout << endl << " "; .RE .RS 0 .RE .RS 2 cout << "Next Permutation: "; .br copy(next_m2.begin(),next_m2.end(), .RE .RS 7 ostream_iterator(cout," ")); .RE .RS 2 cout << endl << endl; .RE .RS 0 .RE .RS 2 return 0; .RE .RS 1 } .br .RE .RS 0 Program Output .RE .RS 0 .br Example 1: .RE .RS 4 Original values: 0 0 0 0 1 0 0 0 0 0 .br Previous permutation: 0 0 0 0 0 1 0 0 0 0 .br Next Permutation: 0 0 0 1 0 0 0 0 0 0 .RE .RS 0 Example 2: .RE .RS 4 Original values: a b c d e f g h j i .br Previous Permutation: a b c d e f g h i j .br Next Permutation: a b c d e f g i h j .SH WARNINGS If your compiler does not support default template parameters, then you always need to supply the \f2Allocator\fP template argument. For instance, you need to write: \f2vector >\fP instead of: \f2vector\fP If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP. .SH SEE ALSO next_permutation