C++ STL algorithm, next_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: Using the C++ next_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++ STL algorithm, next_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, next_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 = 7, ci2 = 5, ci3 = 17;

bool deq1Result;

// container

deque<CInt> deq1, deq2, deq3;

// iterator

deque<CInt>::iterator deq1Iter;

 

// pushing data individually

deq1.push_back(ci1);

deq1.push_back(ci2);

deq1.push_back(ci3);

 

// printing the data

cout<<"deq1 deque of CInts data is: ";

for(deq1Iter = deq1.begin(); deq1Iter != --deq1.end(); deq1Iter++)

cout<<" "<<*deq1Iter<<",";

deq1Iter = --deq1.end();

cout<<" "<<*deq1Iter<<endl;

cout<<"\nOperation: next_permutation(deq1.begin(), deq1.end())"<<endl;

deq1Result = next_permutation(deq1.begin(), deq1.end());

if(deq1Result)

cout<<"The lexicographically next permutation exists and has replaced the original "

<<"ordering of the sequence in deq1 deque."<<endl;

else

cout<<"The lexicographically next permutation doesn't exist and the lexicographically\n"

<<"smallest permutation has replaced the ordering of the sequence in deq1 deque."<<endl;

cout<<"\nAfter the next_permutation, deq1 deque data: ";

for(deq1Iter = deq1.begin(); deq1Iter != --deq1.end(); deq1Iter++)

cout<<" "<<*deq1Iter<<",";

deq1Iter = --deq1.end();

cout<<" "<<*deq1Iter<<endl;

// permuting vector elements with binary function mod_lesser()

//

// container

vector <int> vec1;

// iterator

vector <int>::iterator Iter1;

int i, k =1;

 

for(i = -3; i <= 4; i++)

vec1.push_back(i);

cout<<"\nvec1 vector data: ";

for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl;

next_permutation(vec1.begin(), vec1.end(), mod_lesser);

cout<<"After the first next_permutation(), vec1 vector: ";

for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl;

while (k <= 5)

{

next_permutation(vec1.begin(), vec1.end(), mod_lesser);

cout<<"After another next_permutation() of vec1 vector: ";

for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1 ++)

cout<<*Iter1<<" ";

cout<<endl;

k++;

}

return 0;

}

 

Output examples:

 

deq1 deque of CInts data is: CInt(7), CInt(5), CInt(17)

Operation: next_permutation(deq1.begin(), deq1.end())

The lexicographically next permutation exists and has replaced the original ordering of the sequence in deq1 deque.

After the next_permutation, deq1 deque data: CInt(7), CInt(17), CInt(5)

vec1 vector data: -3 -2 -1 0 1 2 3 4

After the first next_permutation(), vec1 vector: -3 -2 -1 0 1 2 4 3

After another next_permutation() of vec1 vector: -3 -2 -1 0 1 3 2 4

After another next_permutation() of vec1 vector: -3 -2 -1 0 1 3 4 2

After another next_permutation() of vec1 vector: -3 -2 -1 0 1 4 2 3

After another next_permutation() of vec1 vector: -3 -2 -1 0 1 4 3 2

After another next_permutation() of vec1 vector: -3 -2 -1 0 2 1 3 4

Press any key to continue . . .

 

 

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