template<class BidirectionalIterator>
   bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last
   );

template<class BidirectionalIterator, class BinaryPredicate>
   bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
   );

Parameters

_First

A bidirectional iterator pointing to the position of the first element in the range to be permuted.

_Last

A bidirectional iterator pointing to the position one past the final element in the range to be permuted.

_Comp

User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

Return Value

true if the lexicographically next permutation exists and has replaced the original ordering of the range; otherwise false, in which case the ordering is transformed into the lexicographically smallest permutation.

요소들이 미만 비교 가능인 두 구간이 있을 때, lexicographical_compare를 이용해서 그 두 구간을

사전 순으로 비교하는 것은 항상 가능한 일이다.

n개의 요소들로 된 임의의 구간에서, 구별 가능한 순열들의 개수는 유한하다.

구체적으로 말하면 구별 가능한 순열들의 개수는  최대 n!개이다.

그 모든 순열들을 사전 순서로 정렬해서 하나의 테이블 형태로 배치하는 것이 가능하다.

그리고 테이블의 각 순열에 대해, 그 이전 순열과 그 다음 순열에 대한 명확한 정의가 존재한다.

next_permutation은 요소들의 구간 [_first, _last)를 그러한 테이블 안의 다음 순열로,

즉, 사전 순서로 볼 때 다음으로 큰 순열로 변환한다.

그런 순열이 존재하는 경우 next_permutation은 [_first, _last)를 그러한 순열로 변환한 후 true를,

존재하지 않는 경우, [_first, _last)를 사전 순서로 가장 작은 순열로 변환하고 false를 반환.

정의하는 곳

C++ 표준 : <algorithm>

ex) msdn sample

// alg_next_perm.cpp
// compile with: /EHsc
#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>
#include <ostream>

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( )
{
   // Reordering the elements of type CInt in a deque
   // using the prev_permutation algorithm
   CInt c1 = 5, c2 = 1, c3 = 10;
   bool deq1Result;

   deque<CInt> deq1, deq2, deq3;
   deque<CInt>::iterator d1_Iter;

   deq1.push_back ( c1 );
   deq1.push_back ( c2 );
   deq1.push_back ( c3 );

   cout << "The original deque of CInts is deq1 = (";
   copy(deq1.begin(), deq1.end() - 1, ostream_iterator<CInt>(cout, ", "));
   cout << *(deq1.end() - 1) << ")" << endl;

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

   if ( deq1Result )
      cout << "The lexicographically next permutation "
        << "exists and has" << endl
     << "replaced the original ordering of the sequence in deq1."
     << endl;
   else
      cout << "The lexicographically next permutation doesn't exist" << endl
        << "and the lexicographically smallest permutation" << endl
     << "has replaced the original ordering of the sequence in deq1."
     << endl;

   cout << "After one application of next_permutation,\n deq1 = (";
   copy(deq1.begin(), deq1.end() - 1, ostream_iterator<CInt>(cout, ", "));
   cout << *(deq1.end() - 1) << ")" << endl << endl;

   // Permuting vector elements with binary function mod_lesser
   vector <int> v1;
   vector <int>::iterator Iter1;

   int i;

   for ( i = -3 ; i <= 3 ; i++ )
   {
      v1.push_back( i );
   }

   cout << "Vector v1 is ( " ;
   copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
   cout << ")." << endl;

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

   cout << "After the first next_permutation, vector v1 is:\n v1 = ( " ;
   copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
   cout << ")." << endl;

   const int _nRotate = 15;
   int _nVar = 1;

   while ( _nVar <= _nRotate ) {
      next_permutation ( v1.begin ( ) , v1.end ( ) , mod_lesser );
      cout << "After another next_permutation of vector v1,\n v1 = ( " ;
      copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
   cout << ")." << endl;
      _nVar++;
   }