martes, 23 de febrero de 2010

Calculando las permutaciones

Ayer, haciendo un programa para que me haga los pesados determinantes que me mandan en la uni, me enfrente con el problema de que tenia que calcular todas las permutaciones de conjuntos de diferentes tamaños, y después de intentar hacer un programa que calculase todas, decidí buscar un poco, y la verdad es que la mayoría de los algoritmos que me encontré no me valieron de mucho, solo encontré un poco útil este, que no se si sera rápido pero la verdad es que tiene varios inconvenientes como que te da del revés las permutaciones, etc. Y por fin encontre, algo que merece la pena, facil y que me venia como anillo al dedo, se trata de un ejemplo de la web "conclase", pagina muy muy recomendada para aprender c++ y unas cuantas cosas mas.

Funcion + ejemplo

#include <iostream>
using namespace std;

/* Prototipo de función */
void Permutaciones(char *, int l=0);

int main(int argc, char *argv[]) {
   char M[] = "ABCD";

    Permutaciones(M);
    system("pause");
    return 0;
}

void Permutaciones(char * cad, int l) {
   char c;    /* variable auxiliar para intercambio */
   int i, j;  /* variables para bucles */
   int n = strlen(cad);

   for(i = 0; i  < n-l; i++) {
      if(n-l > 2) Permutaciones(cad, l+1);
      else cout  < < cad  < < "\n";
      /* Intercambio de posiciones */
      c = cad[l];
      cad[l] = cad[l+i+1];
      cad[l+i+1] = c;
      if(l+i == n-1) {
         for(j = l; j  < n; j++) cad[j] = cad[j+1];
         cad[n] = 0;
      }
   }
}

Actualizado: 3/05/2010

También existe la posibilidad de usar la función next_permutation() incluida en la librería <algorithm> de c++.

#include 
#include 
using namespace std;

int main ()
{
    int vec[3] = {3,1,2};

    cout << "permutations:" << endl;

    sort (vec,vec+3);

    do cout << vec[0] << vec[1] << vec[2] << endl;
    while ( next_permutation (vec,vec+3) );

    return 0;
}
Comparte o puntua esta publicación ▼

0 comentarios:

Publicar un comentario