C++ STL algorithm, prev_permutation() program sample
Compiler: Visual C++ Express Edition 2005
Compiled on Platform: Windows XP Pro SP2
Header file: Standard
Additional project setting: Set project to be compiled as C++
Project -> your_project_name Properties -> Configuration Properties -> C/C++ -> Advanced -> Compiled As: Compiled as C++ Code (/TP)
Other info: none
To do: How to use the C++ prev_permutation() to re-order the elements in a range so that the original ordering is replaced by the lexicographically next greater permutation if it exists, where the sense of next may be specified with a binary predicate. in C++ programming
To show: How to use the C++ algorithm, prev_permutation() to re-order the elements in a range so that the original ordering is replaced by the lexicographically next greater permutation if it exists, where the sense of next may be specified with a binary predicate. in C++ programming
// C++ STL algorithm, prev_permutation()
#include<vector>
#include<deque>
#include<algorithm>
#include<iostream>
usingnamespace std;
class CInt;
ostream&operator<<(ostream& osIn, const CInt& rhs);
class CInt
{
public:
CInt(int n = 0) : m_nVal(n){}
CInt(const CInt& rhs) : m_nVal(rhs.m_nVal){}
CInt&operator=(const CInt& rhs)
{m_nVal = rhs.m_nVal; return *this;}
bool operator<(const CInt& rhs) const
{return (m_nVal < rhs.m_nVal);}
friend ostream& operator<<(ostream& osIn, const CInt& rhs);
private:
int m_nVal;
};
inline ostream& operator<<(ostream& osIn,const CInt& rhs)
{
osIn<<"CInt("<<rhs.m_nVal<<")";
return osIn;
}
// return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser(int elem1, int elem2)
{
if(elem1 < 0)
elem1 =- elem1;
if(elem2 < 0)
elem2 =- elem2;
return (elem1 < elem2);
};
int main(void)
{
// re-ordering the elements of type CInt in a deque using the prev_permutation algorithm
CInt ci1 = 10, ci2 = 15, ci3 = 20;
bool deq1Result;
// containers
deque<CInt> deq1, deq2, deq3;
// iterator
deque<CInt>::iterator d1_Iter;
int i = 0, j = 0;
// push data individually
deq1.push_back(ci1);
deq1.push_back(ci2);
deq1.push_back(ci3);
// print the data
cout<<"deque with CInts data: ";
for(d1_Iter = deq1.begin(); d1_Iter != --deq1.end(); d1_Iter++)
cout<<*d1_Iter<<",";
d1_Iter = --deq1.end();
cout<<*d1_Iter<<endl;
// do prev_permutation(deq1.begin(), deq1.end()) operation
cout<<"\nOperation: prev_permutation(deq1.begin(), deq1.end())"<<endl;
deq1Result = prev_permutation(deq1.begin(), deq1.end());
if(deq1Result)
cout<<"The lexicographically previous permutation exists and has\nreplaced the original "
<<"ordering of the sequence in deq1."<<endl;
else
cout<<"The lexicographically previous permutation doesn't exist\nand the lexicographically "
<<"smallest permutation\nhas replaced the original ordering of the sequence in deq1."<<endl;
cout<<"\nAfter one application of prev_permutation(), deq1 data is: ";
for(d1_Iter = deq1.begin(); d1_Iter != --deq1.end(); d1_Iter++)
cout<<*d1_Iter<<",";
d1_Iter = --deq1.end();
cout<<*d1_Iter<<endl;
// permutating vector elements with binary function mod_lesser()
//
// container
vector <int> vec;
// iterator
vector <int>::iterator Iter1;
// push data in range
for(i = -4; i <= 4; i++)
vec.push_back(i);
// print data
cout<<"\nvec vector data is: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
// do the prev_permutation(vec.begin(), vec.end(), mod_lesser) operation
cout<<"\nOperation: prev_permutation(vec.begin(), vec.end(), mod_lesser)"<<endl;
prev_permutation(vec.begin(), vec.end(), mod_lesser);
cout<<"After the first prev_permutation(), vec vector is: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
while (j <= 5)
{
prev_permutation(vec.begin(), vec.end(), mod_lesser);
cout<<"After another prev_permutation() of vec vector, vec data is: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1 ++)
cout<<*Iter1<<" ";
cout<<endl;
j++;
}
return 0;
}
Output examples:
deque with CInts data: CInt(10),CInt(15),CInt(20)
Operation: prev_permutation(deq1.begin(), deq1.end())
The lexicographically previous permutation doesn't exist
and the lexicographically smallest permutation
has replaced the original ordering of the sequence in deq1.
After one application of prev_permutation(), deq1 data is: CInt(20),CInt(15),CInt(10)
vec vector data is: -4 -3 -2 -1 0 1 2 3 4
Operation: prev_permutation(vec.begin(), vec.end(), mod_lesser)
After the first prev_permutation(), vec vector is: -4 -3 -2 0 4 3 2 1 -1
After another prev_permutation() of vec vector, vec data is: -4 -3 -2 0 4 3 -1 2 1
After another prev_permutation() of vec vector, vec data is: -4 -3 -2 0 4 3 -1 1 2
After another prev_permutation() of vec vector, vec data is: -4 -3 -2 0 4 2 3 1 -1
After another prev_permutation() of vec vector, vec data is: -4 -3 -2 0 4 2 -1 3 1
After another prev_permutation() of vec vector, vec data is: -4 -3 -2 0 4 2 -1 1 3
After another prev_permutation() of vec vector, vec data is: -4 -3 -2 0 4 1 3 2 -1
Press any key to continue . . .