prev_permutation
Réorganise les éléments dans une plage de sorte que l'ordre d'origine est remplacée par la permutation supérieure lexicographique précédente s'il existe, où le sens du précédent peut être spécifié avec un attribut binaire.
template<class BidirectionalIterator>
bool prev_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool prev_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
Paramètres
_First
Un itérateur bidirectionnel pointant vers la position du premier élément dans la plage à échanger._Last
Un itérateur bidirectionnel pointant sur une position au delà de le dernier élément dans la plage à échanger._Comp
Objet défini par l'utilisateur de fonction de prédicat qui définit le critère de comparaison à répondre par des éléments consécutifs dans l'ordre.Un attribut binaire accepte deux arguments et retourne true si satisfaite et false une fois pas de contenu.
Valeur de retour
true si la permutation lexicographique précédente existe et a substitué l'ordre d'origine de l'intervalle ; sinon false, auquel cas le classement est transformé en la permutation lexicographique la plus grande.
Notes
l'intervalle référencé doit être valide ; tous les pointeurs doivent être deréférençables et dans la séquence la dernière position est accessible dès le début par l'augmentation.
L'attribut binaire par défaut est moins que les éléments dans la plage doivent être inférieur à comparable pour garantir que la permutation précédente est bien définie.
La complexité est linéaire, avec au plus ( _Last – _First) /2 d'échange.
Exemple
// alg_prev_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 = 1, c2 = 5, 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 = 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\n and the lexicographically "
<< "smallest permutation\n has replaced the "
<< "original ordering of the sequence in deq1." << endl;
cout << "After one application of prev_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;
// Permutating 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;
prev_permutation ( v1.begin ( ) , v1.end ( ) , mod_lesser );
cout << "After the first prev_permutation, vector v1 is:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
int iii = 1;
while ( iii <= 5 ) {
prev_permutation ( v1.begin ( ) , v1.end ( ) , mod_lesser );
cout << "After another prev_permutation of vector v1,\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ;Iter1 ++ )
cout << *Iter1 << " ";
cout << ")." << endl;
iii++;
}
}
Configuration requise
en-tête : <algorithm>
l'espace de noms : DST