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

De ASIRodeira

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

Solución de Xavi:

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

Implementación en Java

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

Implementación en Java