Escribir las permutaciones de un nº "n" indefinido de elementos

[fzp]

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).

Código (c) [Seleccionar] Expandir

// 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: ");
scanf ("%d", &n);
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)
{
free (digitos);
printf ("\nTotal permutaciones = %d\n", total_permut); // BORRAR*******
return 0;
}
}
}
}

void imprime (int n, int digitos[])
{
int i;
printf ("%d-", digitos[0]);
for (i = 1; i < n-1; ++i)
printf ("%d-", digitos[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;
}


[Usuario887]

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.

Vengo a examinarte. 

Hace tiempo hice un programa que creo que se basaba en el principio que estas planteando. Era para creackear contraseñas sin diccionarios.

¿Lo que buscas es calcular todas las permutaciones (combinatoria (?)) posibles en un espacio, dado un sistema numerico base? ¿O buscas otra cosa?

No se a que te refieres con "Similitud".

Un saludo.

[fzp]

¿Lo que buscas es calcular todas las permutaciones (combinatoria (?)) posibles en un espacio, dado un sistema numerico base? ¿O buscas otra cosa?

No se a que te refieres con "Similitud".

Lo que el algoritmo pretende es formar, escribir, calcular,... las permutaciones de una colección de "n" objetos (distintos entre sí).

Esa colección (conjunto) de "n" elementos puede ser representada (descrita, asimilada,...) por el subconjunto de números naturales 0, 1,... (n - 1). Por ejemplo, encontrar las permutaciones de las letras "a", "b", "c", es equivalente a encontrar las permutaciones de los números 0, 1, 2; no hay más que establecer la correspondencia: 0-"a", 1-"b", 2-"c". Igual daría "manzana"-"naranja"-"plátano"; ´"n" objetos (distintos) siempre son asimilabes a "n" números enteros (del 0 al n-1).

A su vez, un sistema de numeración en base "n" consta de "n" dígitos (símbolos, objetos,...) mediante los cuales puede escribirse, representarse,... simbólicamente un número natural. Usualmente para base 10 usamos los dígitos 0 - 9, pero si la base es mayor deberemos emplear otros símbolos. Por ejemplo en hexadecimal usamos además del 0 - 9 los símbolos A - F. Pero los símbolos A - F no representan otra cosa que los números 11 - 15 (en decimal). Podríamos representar igual los símbolos a partir del 9 como: (10)-(11)-...-(15). O sea los números naturales del 10 al 15.

Entonces, la "similitud" consiste en que una distribución cualquiera de "n" objetos (distintos entre sí) puede ser representada por "n" símbolos, dígitos,... cada uno de los cuáles representa, a su vez, un número en base "n" que consta de "n" dígitos.

Y una permutación de esos "n" símbolos" (objetos) consistirá simplemente en un número -en base "n"- que consta de "n" dígitos, y en el cual se dé, además, la condición de que todos los ("n") dígitos sean distintos entre sí. Esa es la condición de "caprichosos" a que se refería Serapis en el hilo que me orientó sobre cómo escribir el algoritmo. Son números de "n" dígitos -en base "n"- con la condición "caprichosa" de que todos los dígitos sean distintos entre sí.

Por lo tanto se trata de buscar todos los números de "n" dígitos en base "n" y extraer aquellos cuyos dígitos son todos distintos entre sí; o lo que es lo mismo desechar aquellos que tienen algún digito repetido.

Para ponerlo con un ejemplo. Pretendemos obtener las permutaciones de 3 elementos. Me da igual que sean: a-b-c, que que sea 2-f-X, que que sean manzana-pera-fresa, etc. Al final todas son equivalentes, asimilables... a las permutaciones de 0-1-2.

Pues serán aquellos números de 3 dígitos en base 3, y que además, los dígitos sean distintos y no se repitan. No tengo más entonces que empezar a formar los números de 3 dígitos en base 3 y extraer aquellos cuyos dígitos son todos distintos entre sí.

Empezamos símplemente a "contar" en ese sístema de numeración (3 - dígitos válidos: 0, 1, 2):
000 - No vale: dígitos repetidos
001 - ídem
002 - ídem
010 - ídem
011 - ídem
012 ---- aquí tenemos nuestra 1ª permutación
Seguimos contando (añadiendo +1 a los números)
020 - No vale: dígitos repetidos
021 ---- nueva permutación
Seguimos contando
022 - No vale: dígitos repetidos
100 - idem
101 - ídem
102 ---- nueva permutación
Seguimos contando
110 - No vale: dígitos repetidos
111 - ídem
120 ---- nueva permutación
Seguimos contando
121 - No vale: dígitos repetidos
122 - ídem
200 - ídem
201 ---- nueva permutación
Seguimos contando
202 - No vale: dígitos repetidos
210 ---- nueva permutación
Seguimos contando
211 - No vale: dígitos repetidos
212 - ídem
220 - ídem
221 - ídem
222 - ídem
Ya no se pueden escribir más números de tres digitos en base 3. (25 números en decimal = 2*3^2+2*3^1+2*3^0)

Las permutaciones de tres elementos (para el caso las de los objetos 0-1-2) son:
012 ---- aquí tenemos nuestra 1ª permutación
021 ---- nueva permutación
102 ---- nueva permutación
120 ---- nueva permutación
201 ---- nueva permutación
210 ---- nueva permutación

El algoritmo que escribí simplifica un poco ya que no cuenta desde 0, porque sabemos que la primera permutación (el nº más bajo de "n" dígitos en base "n") es :0-1-2-...-(n-1).
Igualmente sabemos que la 2ª permutación es directamente intercambiar los 2 dígitos de la derecha.
E igualmente sabemos que no es necesario seguir contando hasta el nº: (n-1)-(n-1)-...-(n-1) puesto que sabemos que la última permutación es: (n-1)-(n-2)-(n-3)-...-2-1-0.

Éso sí, no he conseguido simplificar el resto, y por éso lo he hecho a lo bestia: ir sumando de 1 en 1 y a cada nuevo número comprobar si todos sus dígitos son distintos o no.

AL menos el sistema es eficaz, ya que el hecho de que cada nuevo número a comprobar sea distinto del anterior (ya que van aumentando de 1 en 1) nos resguarda de que repitamos permutaciones. Así que si empezamos en la que sabemos que es 1ª, seguimos buscando todas las demás una por una, y paramos en la que sabemos que es última, se supone que debe de darnos todas.

NOTA: la palabra "similitud" es del lenguaje corriente; creo que en un foro de programación se puede entender bastante bien pensando en arreglos. Tengo ya un poco olvidadas mis nociones de álgebra, boole, conjuntos y formulación axiomática (Zermelo) de los numeros naturales; pero si no estoy equivocado, creo que la manera matemáticamente correcta de expresarlo sería que: se puede constatar que existe un isomorfismo entre un conjunto cualquiera (finito) de n elementos (distintos entre sí) y el subconjunto de números naturales 0, 1, 2,..., (n-1).

[Serapis]

Me alegra que hayas captado y entendido correctamente la cuestión. A veces uno explica y cuando no recibe feedback, no te queda claro si acabó entendiendo o intenta deglutirlo o lo ve complejo ydecide pasar del tema...

Hace unos meses, alguien solicitaba una de esas permutaciones caprichosas... como ya tenía una edad avanzada (no es alguien con aspiraciones a nada más que solucionar su problema y ya), tras las explicaciones quedó claro que sin código no iba a saber entender y menos aplicar lo que el explicaba, incluso poniéndole código, así que al final le compartí el proyecto completo. Creo que aún se podrá descargar de donde lo subí, pero si no es así, me lo indicas y lo repongo...

Te sugiero que repases el hilo, es probable que termines de empaparte, además si revisas el código (está en vb.net), podrás ejecutar paso a paso para intentar comprender el modo en que filtro repeticiones e incluso la forma en que establezco otras condicones caprichosas (el filtrado de repetidos no es la única que encaja en esa condición).
Nota que en los primeros mensajes, no se expliucó bien (sule ser habitual), porque las primeras 'soluciones', no resuelven lo que buscaba si no lo uno creía entender que buscaba... a partir del mensaje 9, ya está más enfocado, peor hasta el 18-20 no queda definitivamente aclarado loq eu quiere exactamente...  de todos modos creo que es buena idea leerlo desde el principio para seguir y captar lo que se solicita...
https://foro.elhacker.net/net_c_vbnet_asp/ejercicio_basico_de_combinaciones-t509987.0.html

[Usuario887]

Pues serán aquellos números de 3 dígitos en base 3, y que además, los dígitos sean distintos y no se repitan. No tengo más entonces que empezar a formar los números de 3 dígitos en base 3 y extraer aquellos cuyos dígitos son todos distintos entre sí.

OK, entiendo. Revise el programa que habia mencioado pero no te serviria de nada (es un equivalente a tu funcion cuenta_uno pero en vez de usar ciclos como en ella, yo use recursividad). Me parece que no difiere mucho en eficiencia...

Si se hiciera hardware especifico para esto, se podrian hacer muchas cosas con el, no solo en seguridad.

Suerte en las matematicas caprichosas