Siguiendo las indicaciones aportadas por Serapis en
este hilo sobre la similtud de las permutaciones de "n" objetos con los números -en base "n"- de "n" dígitos, he escrito un código que creo funciona.
Al menos para 3-4 parece que lo hace correctamente; para más me es difícil saberlo porque visualmente y de memoria empiezan ya a ser muchas permutaciones. Pero por el aspecto visual conforme va calculando y por inducción -si funciona para n, debería de funcionar para n+1- parece que sí. Además he añadido unas líneas (no necesarias) para comprobar el nº total de permutaciones (líneas 14, 35, 45) y contrastarlo con n! y también concuerda.
Cosa distinta será la eficacia y por éso quería tener opiniones. Sobre que secuencias de código son poco eficaces y cómo se podrían mejorar. Solo ideas generales, ni siquiera pseudo-código, no estoy pensando en escribir una aplicación como tal sino tener una idea de conjunto de cosas que no se deban hacer en programación.
Yo, algunas me huelo. Por ejemplo yo determino la 1ª y 2ª permutaciones porque la 1ª es el nº menor y la siguiente la misma permutando los dos elementos de menor orden (los 2 de la derecha). Pero a partir de ahí ya voy a saco aumentando 1 el nº y comprobando si es permutación o no. Imagino que (matemáticamente) se podrían saltar varios elementos, dependiendo de la base "n"; pero lo sé.
Otra cosa que me huelo que es mejorable es que yo para determinar si es una permutación o no, yo lo hago a cascoporro, comparo a partir del 2º elemento por la izquierda (el [1]) y hasta el último (el [n-1]) con todos los anteriores, y quizá éso haya formas de mejorarlo comparando por parejas o algo así, no sé.
También tras cada nueva permutación encontrada comprueba si es la última, para no seguir el bucle indefinidamente, pero a lo mejor habría alguna forma de ahorrar comprobaciones. A mí no se me ocurre. Solamente comprobar si el total es = a n!; pero éso no loquiero hacer (el cálculo que he hecho del total es solamente a efectos de contrastar si el código coincide con el nº que debe de salir).
Yo lo he intentado hacer lo más simple y legible posible, pero saber si habría otras maneras de hacerlo más legible o más eficaz. Siempre referido a este tipo de algoritmo, no a los otros que se comentaron en el hilo señalado. (Si me animo igual lo intento con el algoritmo que construye una permut.
siguiente a una dada).
// Escribe las permutaciones de "n" elementos
#include <stdio.h>
#include <stdlib.h>
void imprime (int n, int [] );
void cuenta_uno (int n, int []); // Aumenta 1 unidad al nº en base "n"
int es_permutacion (int n, int []); // Devuelve 1 si es permutación y 0 si no lo es
int main ()
{
int n, i;
int *digitos; // de un nº de "n" dígitos en base "n"
int suma_comprob;
int total_permut = 2; // Solo para comprobar si coincide con n! BORRAR*********
printf ("Introducir nº de elementos a permutar: "); digitos
= (int *) malloc ( n
*sizeof (int) ); for (i = 0; i < n; ++i) // primera permutación
digitos[i] = i;
imprime (n, digitos);
i = digitos[n-2]; // segunda permutación
digitos[n-2] = digitos[n-1];
digitos[n-1] = i;
imprime (n, digitos);
// permutaciones subsiguientes
for (;;)
{
cuenta_uno (n, digitos);
if ( es_permutacion(n, digitos) )
{
imprime (n, digitos);
total_permut += 1; // BORRAR*********
// Comprueba si es última permutación
suma_comprob = 0;
for (i= 0; i < n; ++i)
if (digitos[i] == n-1 - i)
++suma_comprob;
if (suma_comprob == n)
{
printf ("\nTotal permutaciones = %d\n", total_permut
); // BORRAR******* return 0;
}
}
}
}
void imprime (int n, int digitos[])
{
int i;
for (i = 1; i < n-1; ++i)
printf ("%d\n", digitos
[n
-1]); }
void cuenta_uno (int n, int digitos[])
{
int posicion; // digito que se trata en un momento dado: [0], [1],...,[n-1]
posicion = n-1;
if (digitos[posicion] + 1 == n)
do
{
digitos[posicion]= 0;
posicion -= 1;
}
while (digitos[posicion] == n-1);
digitos[posicion] += 1;
}
int es_permutacion (int n, int digitos[])
{
int i, j;
// Se comprueba que todos los digitos[] sean distintos entre sí
for (i = 1; i < n; ++i)
for (j = 0; j < i; ++j)
if (digitos[i] == digitos[j])
return 0;
return 1;
}
Mostrar Mensajes
Y os lo está preguntando para examinaros.
Ahí tienes un mundo; te puede venir muy bien esa latop ya viejita...