C++ Codes
C++ > Visual C++ 5.0 Standard C++ Library sample source codes

The next permutation algorithm changes the order of the elements in the range

The next permutation algorithm changes the order of the elements in the range
The next permutation algorithm changes the order of the elements in the range


next_permutation
	

Header
<algorithm>

template<class BidirectionalIterator> inline
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)

The next_permutation algorithm changes the order of the elements in the range [first, last) to the next lexicographic permutation and returns true. If there is no next_permutation, it arranges the sequence to be the first permutation and returns false. IMPORTANT: The next_permutation algorithm assumes the sequence is sorted in ascending order using operator<. The non-predicate version uses the operator< to order the permutations.

template<class BidirectionalIterator, class Compare> inline
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare compare)

The next_permutation algorithm changes the order of the elements in the range [first, last) to the next lexicographic permutation and returns true. If there is no next_permutation, it arranges the sequence to be the first permutation and returns false. NOTE: The next_permutation algorithm assumes that the sequence is sorted in ascending order using the compare function. The non-predicate version uses the compare function to order the permutations.


Samples
Sample for Non-Predicate Version

// disable warning C4786: symbol greater than 255 character,
// okay to ignore
#pragma warning(disable: 4786)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std ;

void main()
{
    const int VECTOR_SIZE = 3 ;

    // Define a template class vector of strings
    typedef vector<string> StrVector ;

    //Define an iterator for template class vector of strings
    typedef StrVector::iterator StrVectorIt ;

    //Define an ostream iterator for strings
    typedef ostream_iterator<string> StrOstreamIt;

    StrVector Pattern(VECTOR_SIZE) ;

    StrVectorIt start, end, it ;

    StrOstreamIt outIt(cout, " ") ;

    start = Pattern.begin() ;   // location of first
                                      // element of Pattern

    end = Pattern.end() ;       // one past the location last
                                       // element of Pattern

    //Initialize vector Pattern
    Pattern[0] = "A" ;
    Pattern[1] = "B" ;
    Pattern[2] = "C" ;

    // print content of Pattern
    cout << "Before calling next_permutation...\n" << "Pattern: " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << "\n\n" ;

    // Generate all possible permutations

    cout << "After calling next_permutation...." << endl ;
    while ( next_permutation(start, end) )
    {
        copy(start, end, outIt) ;
        cout << endl ;
    }
}

Program Output

Before calling next_permutation:
Pattern: A B C

After calling next_permutation:
A C B
B A C
B C A
C A B
C B A

Sample for Predicate Version

// disable warning C4786: symbol greater than 255 character,
// okay to ignore
#pragma warning(disable: 4786)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std ;

void main()
{
    const int VECTOR_SIZE = 3 ;

    // Define a template class vector of strings
    typedef vector<string> StrVector ;

    //Define an iterator for template class vector of strings
    typedef StrVector::iterator StrVectorIt ;

    //Define an ostream iterator for strings
    typedef ostream_iterator<string> StrOstreamIt;

    StrVector Pattern(VECTOR_SIZE) ;

    StrVectorIt start, end, it ;

    StrOstreamIt outIt(cout, " ") ;

    start = Pattern.begin() ;   // location of first
                                      // element of Pattern

    end = Pattern.end() ;       // one past the location last
                                       // element of Pattern

    //Initialize vector Pattern
    Pattern[0] = "K" ;
    Pattern[1] = "A" ;
    Pattern[2] = "L" ;

    //sort the contents of Pattern, required by next_permutation
    sort(start, end, less<string>()) ;

    // print content of Pattern
    cout << "Before calling next_permutation...\n" << "Pattern: " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << "\n\n" ;

    // Generate all possible permutations

    cout << "After calling next_permutation...." << endl ;
    while ( next_permutation(start, end, less<string>()) )
    {
        copy(start, end, outIt) ;
        cout << endl ;
    }
}

Program Output

Before calling next_permutation:
Pattern: A K L

After calling next_permutation:.
A L K
K A L
K L A
L A K
L K A