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

prev_permutation

Reorganiza los elementos en un intervalo de modo que el orden original se reemplaza por la mayor permutación lexicográficamente anterior si existe, donde el sentido de anterior se puede especificar con un predicado binario.

template<class BidirectionalIterator>
   bool prev_permutation(
      BidirectionalIterator _First, 
      BidirectionalIterator _Last
   );
template<class BidirectionalIterator, class BinaryPredicate>
   bool prev_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 toma dos argumentos y devuelve true cuando se cumple y false cuando no se cumple.

true si la permutación lexicográficamente anterior existe y reemplaza el orden original del intervalo; si no false, en cuyo caso el orden se transforma en la permutación lexicográficamente mayor.

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 menos- que comparable asegurarse que la permutación anterior está bien definida.

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

// 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++;
   }
}
El deque original de CInts es deq1 = (CInt (1), CInt (5), CInt (10)).
La permutación lexicográficamente anterior no existe
 y la permutación lexicográficamente más pequeña
 reemplaza el orden original de la secuencia en deq1.
Después de una aplicación de prev_permutation,
 deq1 = (CInt (10), CInt (5), CInt (1)).

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

Encabezado: <algorithm>

Espacio de nombres: std

Adiciones de comunidad

AGREGAR
Mostrar:
© 2014 Microsoft