next_permutation
Zmienia kolejność elementów w zakresie, tak aby oryginalnego zamówienia otrzymuje brzmienie leksykograficznym dalej permutacji większa, jeśli istnieje, gdzie można określić poczucie dalej z predykatu dwuelementowego.
template<class BidirectionalIterator>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
Parametry
_First
Dwukierunkowy sterująca wskazujące położenie pierwszego elementu w zakresie aby być permutytu._Last
Dwukierunkowy sterująca wskazuje położenie jednego przeszłości ostatniego elementu w zakresie aby być permutytu._Comp
Zdefiniowana przez użytkownika funkcja predykatu obiektu, który definiuje kryterium porównania, muszą być spełnione przez kolejne elementy w kolejności.Predykat dwuelementowy przyjmuje dwa argumenty i zwraca wartość true po spełnieniu oraz false, jeśli nie jest spełniony.
Wartość zwracana
TRUE Jeśli permutacji leksykograficznym dalej istnieje i została wymieniona w oryginalnej kolejności zakres; w przeciwnym razie false, w którym to przypadku porządkowania jest przekształcany w leksykograficznym najmniejszą permutacji.
Uwagi
Zakres odwołania musi być ważny; wszystkie wskaźniki muszą być dereferenceable i w sekwencji ostatniej pozycji jest dostępny z pierwszym przez incrementation.
Predykat dwuelementowy domyślną jest mniejsza niż i elementy w zakresie muszą być mniej niż porównywalne, aby mieć pewność, że następny permutacji jest dobrze określona.
Złożoność jest liniowy, za co najwyżej (_Last-_First) / 2 zamiany.
Przykład
// 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++;
}
}
Wymagania
Nagłówek: <algorytm>
Przestrzeń nazw: std
Zobacz też
Informacje
next_permutation (STL — Przykłady)