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>

using namespace 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 . . .

 

 

C and C++ Programming Resources | C & C++ Code Example Index