Fundamentos:Solucións:Cálculo de Permutacións

Escribir un programa que permita visualizar todas as permutacións dos elementos dunha taboa de caracteres suministrada la liña de comandos.

---

Versión 1

Esta implementación é recursiva e consiste en ir intercambiando o primeiro elemento da cadea e facendo as permutacións da cadea restante.

Pseudocódigo

Partimos da cadea 'orixinal', na que iremos intercambiando o primeiro elemento e aplicando a permutación recursiva a 'cadea' restante:

 Si a Lonxitude da cadea a permutar é 1, visualizar a cadea orixinal
 Se Non
   permuta a cadea a partir de cadea[1]
   i=0
   Mentras que i< lonxitude da cadea a permutar - 1
      intercambia o elemento 0 da cadea co elemento i+1
      permuta a cadea a partir de cadea[1]
      intercambia o elemento 0 da cadea co elemento i+1, (para ter de novo a cadea anterior á permutación)
      i++;
   Fin-Mentras
 Fin-Se

Implementación en C

#include <stdio.h>
#include <string.h>

/* cambio
 *    Recibe: 
 *      A cadea (c), e a posición do elemento a intercambiar co primeiro (i)
 *    Descripción:
 *      Intercambia c[0] con c[i]           
 */
void cambio(char *c,int i)
{
  char t;

  t=c[0];
  c[0]=c[i];
  c[i]=t;
}

/* permuta
 *    Recibe:
 *      A dirección da cadea orixinal (orix), para visualizar o resultado de cada permutación
 *      A dirección da cadea a permutar (cad)
 *    Descripción:
 *      Visualiza as distintas permutacións de cad. Como utiliza a recursión se precisa 
 *      o principio da cadea orixinal para visualizar a secuencia completa.
 */
void permuta(char *orix,char *cad)
{
   int lon;
   int i;
 
   lon=strlen(cad);
   if (lon==1) printf("%s\n",orix);
   else {
     permuta(orix,&cad[1]); // Permutamos a cadea restante (o primeiro elemento é o orixinal)
     for(i=0;i<lon-1;i++) {
        cambio(cad,i+1);  // Intercambiamos o primeiro elemento
        permuta(orix,&cad[1]); // Permutamos a cadea restante
	cambio(cad,i+1);  // Desfacemos o intercambio
     }
   }
}

/* Principal
 *
 */
int main(int argc,char *argv[])
{
  int c;
  char buffer[256];

  if (argc!=2) printf("USO: permuta cadenadeelementos\n");
  else {
     permuta(argv[1],argv[1]);
  }
  return 0;
}

Versión 2

Esta implementación baséase no cálculo dunha permutación concreta baseada nunha serie ordeada de permutacións. Para visualizalas todas bastará visualizar as n! permutacións, sendo n o número de elementos da cadea. Para calcular unha permutación concrete se irá calculando o resto de dividir o número entre 2,3,4,.. o que nos dará os intercambios que teremos que facer e en qué posicións da cadea.

Pseudocódigo

  n=factorial da lonxitude da cadea.
  i=0;
  Mentras (i<n)
    visualiza a permutación i
    i++
  Fin-Mentras

Implementación en C

#include <stdio.h>
#include <string.h>

#define MAXELEMS 50

int p[MAXELEMS];

int fac(int n)
{
  if (n==0) return 1;
  else return n*fac(n-1);
}

void inserta_p(char *c,int a,int b)
{
  char t;

  t=c[b];
  memmove(&c[a+1],&c[a],b-a);
  c[a]=t;
}

void calcula_permuta(int num)
{
  int div=2;
  int x=0;

  while(num>0) {
    p[x]=num%div;
    num=num/div;
    div++;
    x++;
  }
  p[x]=-1;
}

char *efectua_permuta(char *cad,char *cadp)
{
   int x,i;
   int len;

   strcpy(cadp,cad);
   len=strlen(cadp)-1;
   for(x=0;p[x]>=0;x++);
   x--;
   while(x>=0) {
     inserta_p(cadp,len-(x+1),len-(x+1)+p[x]);
     x--;
   }
   return cadp;
}

char *permuta_x(char *cad,char *cadp,int n)
{
   calcula_permuta(n);
   return efectua_permuta(cad,cadp);
}

void permuta2(char *cad)
{
  int i;
  int n=strlen(cad);
  char buffer[256];
  n=fac(n);

  for(i=0;i<n;i++) printf("%s\n",permuta_x(cad,buffer,i));
}

int main(int argc,char *argv[])
{
  int c;
  char buffer[256];

  if (argc!=2) printf("USO: permuta cadenadeelementos\n");
  else {
     permuta2(argv[1]);
  }
  return 0;
}