¿Existe algún algoritmo para escribir las pemutaciones de n elementos sin almacenar las de n-1 elementos?

[fzp]

Pues básicamente lo que quiero saber es éso. Yo sé formar las permutaciones de n elementos a partir de las de n-1 elementos. Solo se necesita partir de la definición de permutación. Si tienes las de n-1 elementos, solo hay que ir intercalando -por ejemplo suponiendo que las tienes escritas con los elementos de izquierda a derecha- el nuevo elemento n desde el lugar 0 hasta el lugar n+1 en todas la permutaciones anteriores de n-1 elementos.

Con lo cual puedes escribir (en teoría) un programa que escriba las permutaciones de cualquier número n de elementos. En realidad serían las permutaciones de n nºs naturales; ya luego tendrías que tener n signos gráficos asociados, pero con con permutar n nºs enteros (considerados como números no como dígitos) bastaría.

Así, para cualquier número n bastaría ir calculando/escrbiendo las permutaciones de 2 elementos, a partir de ellas las de 3 elelementos , y así sucesivamente hasta las de n elementos.

Pero claro, tienes que tener capacidad de almacenaje de las permutaciones de un número de elementos creciente, que además con las permutaciones es brutal; crece factorialmente.

Por eso me he preguntado si existiría un algoritmo que no necesitase almacenar las permutaciones de n-1 elementos, sino que solo mediante bucles fuese capaz de escribir las permutaciones directamente. De existir tal cosa podría ponerse el programa a trabajar, y aunque al final a la larga sería lo mismo, puesto que las permutaciones habría que o guardarlas en disco o guardarlas en papel, y el tiempo de trabajo del programa crecería hasta infinito -según le pidieras permutaciones de un nº creciente de elementos-; pero al menos, no colapsaría previamente por falta de almacenamiento. En todo caso colapsaría en el tiempo.

Yo le he dado algunas vueltas al asunto y creo que no, que no es posible tal algoritmo, y que cualquier algoritmo pasa por tener almacenadas las permutaciones de n-1 elementos para poder calcular las de n elementos. Pero como sé que -en esto- no paso de ser una medianía por eso pregunto.

¿Habría alguna manera de ir reproduciendo las permutaciones de un nº cualquiera de nºs naturales? ¿Sólo mediante bucles o algo así sin almacenar las de un nº de elementos anteriores?

----------------------------

A raíz de esta pregunta me surgió otra que, en puridad, debería estar en un foro diferente, el de Dudas Generales, o algo así. Pero bueno por no complicar la dejo aquí.
Y es: ¿existe alguna aplicación práctica (Ingeniería, Física... lo que sea) que necesite tener las permutaciones de un nº variable elementos?
NO el nº de permutaciones, que si sé que éso se emplea, desde la Física Termodinámica Estadística, pasando por la Mecánica Cuántica, hasta disciplinas probabilísticas. No, no el nº de permutaciones, sino las permutaciones en sí mismas. ¿Hay alguna aplicación práctica que las necesite?

[Serapis]

Por eso me he preguntado si existiría un algoritmo que no necesitase almacenar las permutaciones de n-1 elementos, sino que solo mediante bucles fuese capaz de escribir las permutaciones directamente.

Yo le he dado algunas vueltas al asunto y creo que no, que no es posible tal algoritmo, y que cualquier algoritmo pasa por tener almacenadas las permutaciones

Las permutaciones, son bases numéricas con condicionantes algo 'caprichosos'.
Del mismo modo que puedes escribir 78 directamente en sistema decimal, sin necesidad de tener todas las permutaciones de 2 dígitos previas (00-77), igual pasa con cualquier otra base numérica.

Todo lo que necesitas saber de antemano es cuantos elementos contiene (el numero mayor para x dígitos), o dicho de otra manera que número de secuencia supone la última secuencia buscada (con dos dígitos es 99, luego son 100 permutaciones).
Después de eso, es exactamente lo mismo que operar con cualquier base numérica.

Intenta pasar el numero 78 de la base decimal a una base 12, 17 o 44... cuando te suene familiar, te será más fácil entenderlo y resolverlo.

[kub0x]

Y es: ¿existe alguna aplicación práctica (Ingeniería, Física... lo que sea) que necesite tener las permutaciones de un nº variable elementos?
[...] No, no el nº de permutaciones, sino las permutaciones en sí mismas. ¿Hay alguna aplicación práctica que las necesite?

En Matemáticas, especialmente la Criptografía utilizamos transformaciones lineales sobre un campo finitio las cuales son permutaciones lineales, es decir, a todo vector le corresponde otro bajo la salida de L(X). Pero la permutación es una matriz.

También tienes el sistema factoradic (que ya existía cuando lo re-descubrí) que no es más que una translacción del sistema decimal al sistema factorial. Con esto sacamos una lista de cocientes, que nos indican el ordenamiento de los elementos a los que le aplicamos la permutación.
Es que de hecho, si ves cualquier tabla de Cayley, ahi tienes permutaciónes en si mismas, tal como preguntas. Tiene aplicaciones vitales, y entender permutaciones es entender teoría de grupos y algebra ábstracta, ya que normalmente los grupos son derivables a un grupo de permutaciones (Group Action & Group representation).

Saludos.

[fzp]

Gracias. No sabía nada de esas aplicaciones, kub0x. Es bueno enterarse.

Por otro lado, en cuanto a un algoritmo para escribir/calcular permutaciones -sin almacenar las previas-, viendo las indicaciones de Serapis y lo que subyace debajo de ellas, sí que empiezo a vislumbrar, aunque de un modo borroso, cómo podría hacerse posible.

La idea de ver las permutaciones de n elementos como aquellos números de n dígitos en un sistema de base n en los cuáles todos los dígitos son distintos, me parece muy ingeniosa. Yo nunca las había visto así porque siempre me quedé con la idea de cómo me las explicaron. Que  simplemente son las formas de cambiar de sitio n elementos. Y por eso siempre había pensado que la única forma de encontrarlas era combinar las de los elementos anteriores (n-1 elementos) e intercalando el nuevo elemento n en las distintas posiciones (huecos entre cada dos elementos) de cada una de aquellas.

Después de lo que dijo Serapis, ahora sí que entreveo como podría ser el algoritmo. Todavía algo inconcreto, pero veo más o menos cómo. Para un nº n cualquiera de elementos sería algo parecido a ésto: se trataría de formar los números de n dígitos en un sistema de base n e ir contando de 1 en 1 y descartando aquellos que tienen algún dígito repetido. Se organizarían en un sólo arreglo que se iría actualizando, no necesitando más capacidad de almacenaje.

No se empezaría en 0 sino en el nº: (0)-(1)-...-(n-2)-(n-1), que sería la primera permutación; la que corresponde al orden natural de los dígitos; el nº menor -cuyos dígitos no se repiten- en ese sistema de numeración.

Luego se iría contando de 1 en un 1 en una forma de conteo natural en ese sistema de base n. Con conteo natural quiero decir la forma en que se supone que se cuenta en cualquier sistema; como si fuesen ruedas (posiciones) con n símbolos (en este caso serían los nºs naturales 0,1,...,(n-1); y cuando en una posición la rueda alcanza el (n-1), el siguiente nº pasa a ser 1 en la posición de la izquierda y 0 en la actual.

Otra forma de hacerse podría ser que el programa contase de 1 en 1 (sumando +1) en decimal, y luego realizar la conversión a base n mediante divisiones sucesivas y considerar restos y el último cociente pero, además de no ser muy elegante (programáticamente hablando) creo que sería más ineficiente que realizar el conteo natural al sistema de base n, ya que el el nº en decimal podría producir overflow según el sistema que el compilador use para almacenar nºs enteros.

El bucle no tendría que llegar hasta el nº (n-1)-(n-1)-...-(n-1) porque lo pararíamos de dos posibles formas:
- de forma natural en la permutación/número (n-1)-(n-2)-(n-3)-...-(1)-(0) que sabemos que es la última (para lo cual tras cada nueva permutación habría que realizar la comprobación de si es la última)
- o bien con un contador -en decimal- que añadiría 1 unidad cada vez que encontrásemos una nueva permutación y que se detendría al llegar a n! (en decimal). Por la misma razón que antes parece mucho más elegante la 1ª forma.

Para entresacar las permutaciones, tras cada aumento +1 en el conteo habría que realizar un bucle que fuese comparando los dígitos de ese número desde el 1º con cada uno de los siguientes para ver si se repite alguno. En el momento en que alguno se repitiese se suspendería el bucle ya que no sería una permutación, y se pasaría al bucle de contar +1; si se consiguiese completar sin repeticiones se imprimiría en pantalla como nueva permutación (o en papel o en disco) y se seguría contando con el bucle de +1.

Creo que algo así funcionaría, aunque fuese poco eficiente. Yo mismo veo que por ejemplo se podría mejorar pasando de la 1ª permutación a la 2ª saltándose varios números. Y sospecho que los matemáticos tienen formas de encontrar los intervalos en que van apareciendo las permutaciones según el valor de n para saltarse la comprobación de si se repiten dígitos.

-------------

Aparte de ésto también he investigado y he visto que existen otros algoritmos. Por ejemplo he encontrado estas webs interesantes:

https://es.wikipedia.org/wiki/Algoritmo_de_Heap

https://books.google.es/books?id=Y2k9DwAAQBAJ&pg=PA285&lpg=PA285&dq=algoritmo+formacion+de+permutaciones&source=bl&ots=ADM70HNb0v&sig=ACfU3U0XyInRCC84kX2YXVKp-DZ3T2hFyw&hl=es&sa=X&ved=2ahUKEwiL3IziiNzzAhUCcBQKHZ8CC9MQ6AF6BAgTEAM#v=onepage&q=algoritmo%20formacion%20de%20permutaciones&f=false

Por lo visto es muy eficiente el 1º pero a mi me ha llamado mucho la atención el 2º. Parece ser que en el conjunto de las permutaciones puede establecerse una relación de orden (a la que llaman lexicográfico) y que existe un algoritmo para encontrar la permutación siguiente a una dada (y además de forma bastante fácil y por tanto fácil de programar) y por tanto, como sabemos cuál es la 1ª permutación podemos construir las siguientes con el algoritmo para detectar la siguiente,... y así sucesívamente; y como también sabemos cuál debe de ser la última podemos abortar el programa.

Así que como el hilo iba de si existía algún algoritmo que no necesitase almacenar las permutaciones previas y veo que sí que existe (y no uno sino varios), que era lo que me interesaba -más allá del propio algoritmo- doy por solucionado el tema.