Buscando por ahà descubrà recientemente que se puede usar la STL del C++ para generar permutaciones de los contenidos de un vector, lo cual resulta muy útil cuando nos encontremos con problemas que pueden reducirse a la búsqueda de un ciclo hamiltoniano. No obstante con este tipo de problemas hay que ir con bastante cuidado y optimizar lo que se pueda ya que el problema del ciclo hamiltoniano pertenece a la clase de complejidad NP-Completo. Esto a efectos prácticos te dice que hagas lo que hagas el problema genérico no va a librarse de un coste exponencial. De hecho intentar resolver el problema del ciclo hamiltoniano con este método para más de unos 12 ó 13 valores distintos se saldrá casi seguro de los 10 segundos del UVA y ni que decir del segundo de USACO.
Os pongo aquà el código que hice para probar el método:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, char *argv[]) {
vector<int> v;
vector<int>::iterator start, end, it;
for(int i=1;i<=4;i++) v.push_back(i);
start = v.begin();
end = v.end();
do {
for(it=v.begin();it!=v.end();it++) cout << *it << " ";
cout << endl;
} while(next_permutation(start, end));
return 0;
}
Este código genera e imprime las posibles permutaciones de un vector de enteros que contiene los números del 1 al 4. Igual que con enteros, puedes usar cadenas o los objetos que te de la gana si sobrecargas los operadores de comparación adecuadamente. Además, si por ejemplo cambiamos
start = v.begin(); por
start = ++v.begin();, observaremos que el primer elemento del vector, el 1, queda fijo y se generan las permutaciones variando sólo los demás.
Personalmente no habÃa visto nunca ese #include <algorithm> antes. ¿Conocéis más usos útiles del mismo?
PD: lo probé a usar para un problema del UVA y no dio ningún error de compilación, asà que allá está también. Lo que sà me dio es un time limit excedeed (y no me extraña para lo que era).
Portal
Suscribete
Programación
