La millonésima permutación lexicográfica

De nuevo Project Euler, tal vez con el programa más difícil que me he encontrado hasta ahora. Desde que empecé a programar, la recursión (recursividad o recurrencia) me ha parecido de las formas más difíciles y sin embargo más elegantes de programar (programación funcional). Para hacer permutaciones me parece inevitable utilizar recursión. Cito el problema 24 de Project Euler:

Una permutación es una disposición ordenada de objetos. Por ejemplo, 3124 es una  posible permutación de los dígitos 1, 2, 3, 4. Si todas las permutaciones se listan numérica o alfabéticamente, a esta disposición le llamamos orden lexicográfico. Las permutaciones lexicográficas de 0, 1, 2 son: 012   021   102   120   201   210. ¿Cuál es la millonésima permutación lexicográfica de los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9?

El problema parece sencillo; después de programar los problemas 19 y 28 de forma casi trivial, me topé con este problema que simplemente no podía lograr. Prácticamente siempre empiezo un programa de la forma más sencilla, lo pruebo así y lo llevo después a la forma complicada. El ejemplo que da Project Euler puede resultar engañoso, y como yo, cualquiera puede caer en un pozo sin fondo.

Sabemos que el número de permutaciones posibles de un conjunto de $n$ objetos es igual a $n!=n\cdot(n-1)\cdot3\cdot2\cdot1$. El problema de comenzar con casos sencillos, es que, por ejemplo para $n=3$, un simple bucle anidado de 2 niveles es suficiente para repetir 3 veces un bucle que se repite 2 veces, obteniendo las $3!=6$ permutaciones buscadas, en cambio, si tomamos el caso $n=4$, necesitaríamos un bucle de 3 niveles que hiciera 4 veces un bucle que repite 3 veces otro bucle que se repite 2 veces, obteniendo $4!=24$ permutaciones... y así sucesivamente para cualquier $n$ usando este razonamiento, lo cual no es práctico ni mucho menos, recordando que el problema que queremos resolver nos pide $10!$ permutaciones.

Bueno, pues ya que sabemos que se obtendrán $10!$ permutaciones, debemos recordar cómo utilizar la técnica de recursividad. Regularmente cuando se introduce este concepto se utiliza el ejemplo del factorial. En Python se ve algo así:

def f(n):
        if n > 1 :
            return (n*f(n-1))
        else:
            return 1

Bien pues se necesita usar este tipo de razonamiento pero buscando formar permutaciones. Una buena forma de lograrlo es intentarlo primero con un conjunto de cuatro objetos, lo más sencillo a empezar con 0123. Un razonamiento que funciona es intercambiar un par externo e ir avanzando hacia el siguiente término, como se observa el patrón que a continuación muestro. Las primeras permutaciones se verían así:

0123
0132
0213
0231
0312
0321
1023
1032
1203
1230
1302
1320
2013
$\vdots$

Notamos fácilmente que para la primer posición de izquierda a derecha, el 0 se mantiene fijo y los términos adyacentes permutan $6=3!$ veces, y de igual modo, si nos fijamos en la posición siguiente, en todas las permutaciones que comienzan con 0, cada objeto tiene $2=2!$ permutaciones, y esto fácilmente lo podemos predecir para cualquier combinación siguiente. Si observáramos una posición aún anterior, veríamos que 0, 1, 2, y 3 forman exactamente $4!$ permutaciones, que es lo que buscamos. También es fácil notar que no necesitamos ordenar permutaciones para formar un orden lexicográfico si comenzamos con una cadena ordenada, i.e. 0123456789.

Ahora el trabajo arduo (al menos para mí lo fue) es describir esto en un lenguaje estricto y obtener lo que se busca. Recomiendo primero encontrar el patrón que describen las permutaciones y luego intentar codificarlo. Casi siempre que resuelvo un nuevo problema de Project Euler parece que ha sido el más retador, sin embargo éste se ha llevado definitivamente el título, además de que la recursividad como dije, no me parece algo tan sencillo.

Python (y supongo que otros lenguajes más) tienen funciones predefinidas que dan permutaciones, sin embargo ¿qué de divertido habría en sólo buscar la millonésima de éstas, o si acaso tener que ordenar las permutaciones?.

Este tipo de problemas es digno de discusión con profesores o colegas/compañeros si es que te estancas; en mi caso pasé 2 días y 2 noches pensando y lidiando con la recursividad, aunque el patrón sea muy sencillo de descifrar.

Mi código es un tanto feo aunque no es tan largo y tuve algunos problemas con las posiciones del arreglo que contiene cada permutación. Dentro del programa cree un archivo en el cual escribí las permutaciones y al final la millonésima permutación lexicográfica, lo que como vimos arriba sería innecesario considerando que $10!>1,000,000$ pudiéndonos detener entonces antes de que el programa se ejecute totalmente.

Aquí dejo las permutaciones del conjunto 012345678 para que te puedas guiar con más datos acerca del patrón formado y el algoritmo que debes codificar.

HAPPY CODING!

:)