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_Heaphttps://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=falsePor 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.