next_permutation

Article
06/09/2015

Réorganise les éléments d'une plage de sorte que le classement d'origine est remplacée par la permutation supérieure lexicographique suivante s'il existe, où le sens de mai prochain est spécifiée avec un attribut binaire.

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

Paramètres

_First
Un itérateur bidirectionnelle qui pointent vers la position du premier élément dans la plage à échanger.
_Last
Un itérateur bidirectionnelle qui pointent vers la position une après l'élément final dans la plage à échanger.
_Comp
Objet de la fonction définie par l'utilisateur de prédicat qui définit les critères de comparaison à répondre par des éléments consécutifs dans une classe. Un prédicat binaire a besoin de deux arguments. Il renvoie true lorsqu'il est satisfait et false dans le cas contraire.

Valeur de retour

si latrue permutation lexicographique suivante existe et a remplacé l'ordre d'origine de la plage ; sinon false, auquel cas l'ordre est transformé cette permutation lexicographique la plus petite.

Notes

La plage référencée doit être valide ; tous les pointeurs doivent être deréférençables et dans la séquence la dernière position est accessible la collection contenue par l'augmentation.

L'attribut binaire par défaut est inférieure et les éléments de la plage doivent être inférieure à comparable à assurer que la permutation suivante est correctement définie.

Complexité un-à-un avec au plus(_Last – _First)/2 échanges.

Exemple

// 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 = (";
   for ( d1_Iter = deq1.begin( ); d1_Iter != --deq1.end( ); d1_Iter++ )
      cout << " " << *d1_Iter << ",";
   d1_Iter = --deq1.end( );
   cout << " " << *d1_Iter << " )." << endl;

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

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

   cout << "After one application of next_permutation,\n deq1 = (";
   for ( d1_Iter = deq1.begin( ); d1_Iter != --deq1.end( ); d1_Iter++ )
      cout << " " << *d1_Iter << ",";
   d1_Iter = --deq1.end( );
   cout << " " << *d1_Iter << " )." << 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 ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

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

   cout << "After the first next_permutation, vector v1 is:\n v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   int iii = 1;
   while ( iii <= 5 ) {
      next_permutation ( v1.begin ( ) , v1.end ( ) , mod_lesser );
      cout << "After another next_permutation of vector v1,\n v1 =   ( " ;
      for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ;Iter1 ++ )
         cout << *Iter1  << " ";
      cout << ")." << endl;
      iii++;
   }
}

Configuration requise

En-tête : <algorithme>

Espace de noms : std

Voir aussi

Référence

next_permutation (Exemples STL)

Version avec prédicat de next_permutation

Bibliothèque STL (Standard Template Library)

Partager via