Exportar (0) Imprimir
Expandir todo
Este artículo proviene de un motor de traducción automática. Mueva el puntero sobre las frases del artículo para ver el texto original. Más información.
Traducción
Original

next_permutation

Reorganiza los elementos en un intervalo de modo que el orden original se reemplaza por la mayor permutación lexicográficamente siguiente si existe, donde el sentido para el próximo pueden se especifica con un predicado binario.

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

_First

Un iterador bidireccional que apunta a la posición del primer elemento del intervalo que se permutará.

_Last

Un iterador bidireccional que apunta a la posición una más allá del último elemento en el intervalo que se permutará.

_Comp

Objeto definido por el usuario de la función de predicado que define el criterio de comparación que se completará por los elementos sucesivos del orden. Un predicado binario acepta dos argumentos y devuelve true cuando se cumple y false cuando no se cumple.

true si la permutación lexicográficamente siguiente existe y reemplaza el orden original del intervalo; si no false, en cuyo caso el orden se transforma en la permutación lexicográficamente más pequeña.

El intervalo hace referencia debe ser válido; todos los punteros deben ser dereferenceable y dentro de la secuencia la posición última es accesible de primera por el aumento.

El predicado binario predeterminado es menor que y los elementos del intervalo deben ser menor que comparable garantizar que la permutación siguiente está bien definida.

Complejidad es lineal con como máximo (_Last – _First)/2 intercambios.

// 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++;
   }
}
El deque original de CInts es deq1 = ( CInt( 5 ), CInt( 1 ), CInt( 10 ) ).
La permutación lexicográficamente siguiente existe y tiene
reemplazó el orden original de la secuencia en deq1.
Después de una aplicación de next_permutation,
 deq1 = (CInt (5), CInt (10), CInt (1)).

El vector v1 es (-3 -2 -1 0 1 2 3).
Después del primer next_permutation, el vector v1 es:
 v1 = (-3 -2 -1 0 1 3 2).
Después de otro next_permutation vectoriales v1,
 v1 = (-3 -2 -1 0 2 1 3).
Después de otro next_permutation vectoriales v1,
 v1 = (-3 -2 -1 0 2 3 1).
Después de otro next_permutation vectoriales v1,
 v1 = (-3 -2 -1 0 3 1 2).
Después de otro next_permutation vectoriales v1,
 v1 = (-3 -2 -1 0 3 2 1).
Después de otro next_permutation vectoriales v1,
 v1 = (-3 -2 -1 1 0 2 3).

Encabezado: <algorithm>

Espacio de nombres: std

Adiciones de comunidad

AGREGAR
Mostrar:
© 2014 Microsoft