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

De Wiki do Ciclo ASIR do IES de Rodeira

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


Índice

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;
}