Xavi: Nova páxina: "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 imple..."

2014-06-26T11:04:57Z

Nova páxina: "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 imple..."

Páxina nova

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:

<source lang='text'>
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
</source>

===== Implementación en C =====
<source lang='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;
}

</source>

==== 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 =====
<source lang='text'>
n=factorial da lonxitude da cadea.
i=0;
Mentras (i<n)
visualiza a permutación i
i++
Fin-Mentras
</source>

===== Implementación en C =====
<source lang='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;
}
</source>

Fundamentos:Solucións:Cálculo de Permutacións - Historial de revisións

Xavi: Nova páxina: "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 imple..."