Particiones enteras

Celebrando el hecho de que ya termino con mi primer ciclo de la maestría, y que ademas he conseguido el titulo de experto en ProjectEuler haré un post acerca de un problema que me parece interesante. El enunciado es bien simple:

Dado un numero entero "n" ¿De cuantas maneras diferentes se puede descomponer "n" en números enteros positivos?.

La solución aunque simple no es evidente.
Por ejemplo, sea n = 4.
4 puede descomponerse en: ( 1 + 1 + 1 + 1 ), ( 1 + 2 + 1 ), ( 3 + 1 ), ( 2 + 2 ) y ( 4 ). Cada una de estas sumas es una partición entera de 4. Como buscamos solo particiones diferentes hay algunas que no se consideran, por ejemplo, no se esta considerando ( 2 + 1 + 1 ) porque es lo mismo que ( 1 + 1 + 2 ) si ignoramos el orden.
Es fácil entender de donde viene el nombre de partición entera, lo que estamos haciendo es "partir" el numero 4 en agrupaciones diferentes:
Vemos que el numero de formas diferentes en que se puede descomponer 4 es 5.

La función que devuelve el numero total de particiones diferentes de un numero "n" se denota como p(n), entonces: p(4) = 5. ¿Como hacemos para calcular p(n) para un "n" cualquiera? Antes de resolver este problema resolveremos el problema mas general:

Dado un numero entero "n", listar todas las particiones enteras diferentes de "n".
La clave para resolver este problema es considerar particiones ascendentes y ordenadas de menor a mayor.
Una partición ascendente (que abreviaremos: PA) es aquella en la cual se cumple que cada termino es igual o mayor que el termino a su izquierda; así ( 1 + 1 + 2 ) es una PA, pero ( 1 + 2 + 1 ) no lo es.

Una partición es mayor que otra partición si su n-ésimo termino es mayor que el n-ésimo termino de la otra partición (cuando se lee de izquierda a derecha), siendo todos los términos anteriores al n-ésimo iguales (si existen). De aquí que ( 1 + 3 ) sea mayor que ( 1 + 1 + 2 ) porque su segundo termino es mayor que el segundo termino de la otra.

Ordenando las particiones ascendentes para n = 4:

1. pa1 = 1 + 1 + 1 + 1
2. pa2 = 1 + 1 + 2
3. pa3 = 1 + 3
4. pa4 = 2 + 2
5. pa5 = 4
   

Iterativamente no se cómo se pueda generar esta secuencia así que iremos por el camino recursivo. De la lista de arriba podemos ver que las particiones ascendentes de 4 son:

PA de 4 = (pa1 + pa2 + pa3) + (pa4) + (pa5)

o dicho de otra manera:

PA de 4 = (PA de 4 que empiezan con 1) + (PA de 4 que empiezan con 2) + (PA de 4 que empiezan con 4)

Sea f una función recursiva que devuelva particiones ascendentes. Si esta función recibiera como primer parámetro una partición ascendente con la que queremos que empiecen todas las particiones ascendentes devueltas por esta función, podríamos escribir la igualdad anterior como:

PA de 4 = f({1}, ...) + f({2}, ...) + f({4}, ...) -- (1)

Donde usamos las llaves { } para indicar los términos de una partición. Estamos considerando que f puede recibir otros parámetros (que aun no hemos descubierto) y por eso le agregamos los puntos consecutivos como segundo parámetro.

Para resolver este problema es vital darse cuenta que todas las particiones de 4 pueden a su vez ser generadas por la misma función pero enviándole como primer parámetro una partición vacía:

PA de 4 = f({}, ...) -- (2)

Examinando la ecuación (1) vemos que falta el termino f({3}, ...) que correspondería a las particiones ascendentes de 4 que empiezan con 3. De nuestra lista de particiones (al inicio) vemos que no existe ninguna, pero razonemos porque; si existiera alguna PA esta sería de la forma: ( 3 + ... ), ya que 3 es menor que 4 entonces aun tenemos que agregarle mas términos, pero los únicos valores que podemos agregar como siguientes términos serian números iguales o mayores que 3 (porque tiene que ser una PA) entonces la lista de posibles particiones seria: ( 3 + 3 ), ( 3 + 4 ), etc. Todas ellas con sumas mayores que 4, lo que no puede ser, de aquí que:

f({3}, ...) = ∅ (conjunto vacío)

Agregando esto a (1):

PA de 4 = f({1}, ...) + f({2}, ...) + f({3}, ...) + f({4}, ...) -- (3)

Remplazando (2) en (3):

f({}, ...) = f({1}, ...) + f({2}, ...) + f({3}, ...) + f({4}, ...) -- (4)

Nos falta una forma de pasar la información del número de quien estamos generando particiones (en nuestro ejemplo de 4). Para esto podemos pasar como segundo parámetro el valor que queremos que sumen los términos que se agreguen a la PA que pasamos como primer parámetro, agregando esto a (4):

f({}, 4, ...) = f({1}, 3, ...) + f({2}, 2, ...) + f({3}, 1, ...) + f({4}, 0, ...) -- (5)

en donde:

f({1}, 3, ...) = ( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 ), ( 1 + 3 )
f({2}, 2, ...) = ( 2 + 2 )
f({3}, 1, ...) = ∅ (conjunto vacío)
f({4}, 0, ...) = ( 4 )

Aquí f({1}, ...) se ha convertido en f({1}, 3, ...) porque si cada PA empieza con 1 (y buscamos las PA de 4), solo necesitamos agregar términos hasta que sumen 3:

PA de 4 que empiezan con 1 = f({1}, 3, ...) = ( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 ), ( 1 + 3 )

Ya estamos preparados para investigar el comportamiento recursivo de f, vemos que:

f({1}, 3, ...) = [( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 )], [ ∅ ], [( 1 + 3 )]

o en palabras:

PA de 4 que empiezan con {1} = (PA de 4 que empiezan con {1, 1}) + (PA de 4 que empiezan con {1, 2}) + (PA de 4 que empiezan con {1, 3})

en donde:

f({1, 1}, 2, ...) = ( 1 + 1 + 1 + 1 ), ( 1 + 1 + 2 )
f({1, 2}, 1, ...) = ∅ (conjunto vacio)
f({1, 3}, 0, ...) = ( 1 + 3 )

o en términos de f :

f({1}, 3, ...) = f({1, 1}, 2, ...) + f({1, 2}, 1, ...) + f({1, 3}, 0, ...) -- (6)

De (5) y (6) podemos obtener pistas de como terminar la recursion, observemos que:

f({4}, 0, ...) = ( 4 )
f({1, 3}, 0, ...) = ( 1 + 3 )

Es simple deducir de estos ejemplos que si nos pasan como segundo parámetro cero, significa que no necesitamos agregar nada a la lista que nos pasaron como primer parámetro (pues ya suma lo que estábamos buscando), y solo debemos retornar esa lista como respuesta y terminar la recursión, entonces:

f(pa, 0, ...) = pa -- (7)

en donde:

pa = alguna partición ascendente

Además de:

f({3}, 1, ...) = ∅ (conjunto vacio)
f({1, 2}, 1, ...) = ∅ (conjunto vacio)

se puede deducir que si el segundo parámetro es un numero menor que el último termino de la PA pasada como primer parámetro, entonces la función debe retornar nada y terminar:

f(pa, m, ...) = ∅ (conjunto vacío) Si (m < z) ∧ (m > 0) -- (8)

en donde:

z = último termino de pa.

Es fácil demostrar esto ya que los únicos elementos que podemos agregar a pa = {a, b, ... , z} son números iguales o mayores que z, y como m > 0 aún tenemos que agregar términos a pa (pues no esta completa), pero agregando cualquiera de los términos válidos nos dará una suma mayor que m (porque los términos validos son por lo menos iguales a z y z > m) lo que no se quiere.

De (5) y (6):

f({}, 4, ...) = f({1}, 3, ...) + f({2}, 2, ...) + f({3}, 1, ...) + f({4}, 0, ...)
f({1}, 3, ...) = f({1, 1}, 2, ...) + f({1, 2}, 1, ...) + f({1, 3}, 0, ...)

Es posible deducir que:

f(pa, m, ...) = f({pa, z}, m - z, ...) + f({pa, z + 1}, m - z - 1, ...) + ... + f({pa, m}, 0, ...) -- (9)

en donde:

pa = alguna partición ascendente
z = último termino de pa, o 1 si pa esta vacía.
m > 0 ∧ m ≥ z

La ecuación (9) dice que todas las PA que empiezan con pa (y a las que hay que agregar términos hasta que sumen m) son iguales a la sumatoria de todas las PA que empiezan con pa mas un termino (que va desde z hasta m, donde z es el ultimo termino de pa) en donde se resta el nuevo termino a la suma a la que deben llegar los nuevos términos de las nuevas particiones. Como vemos pa crece en tamaño y m disminuye en valor, siendo evidente por (7) y (8) que este proceso recursivo debe llegar a un fin.

Ademas de (7), (8) y (9) vemos que ya no serán necesarios mas parámetros para esta función pues ya hemos establecido su proceso iterativo y condiciones para detener la recursión.

Resumiendo:

f(pa, m) = f({pa, z}, m - z) + f({pa, z + 1}, m - z - 1) + ... + f({pa, m}, 0) Si (m ≥ z) ∧ (m > 0)
f(pa, m) = ∅ Si (m < z) ∧ (m > 0)
f(pa, m) = pa Si (m = 0)

en donde:

pa = alguna partición ascendente
z = último termino de pa, o 1 si pa esta vacía.

La relación recursiva puede escribirse en forma compacta:

Listo!, ya tenemos todo lo necesario para programar.
Usaremos arreglos para representar las particiones e iremos imprimiendo las particiones que vayamos encontrando (no las devolveremos). En código simplificado:

void f(pa, m) {
    // Determinar valor de [z].
    z = (pa.longitud() > 0)? pa.ultimo() : 1 

    // Proceso recursivo
    for (k = z; k <= m; ++k) {
        // Crear nueva particion temporal [pt] agregando 
        // elemento [k] a la particion [pa].
        pt = pa.agregarAlFinal(k)
        
        if (m == k) {
            // Si (m - k == 0) imprimir [pt]
            imprimir(pt) 
        }
        else {
            // Continuar recursion
            f(pt, m - k)
        }
    }
}

Puedes revisar la implementación online en AS3 aquí, los comentarios están en ingles, pero son similares a los comentarios de arriba.

Lamentablemente la solución que he implementado es bastante lenta para valores de n grandes. Los métodos de optimización serán motivo de otro post, incluyendo la historia de como ese genio entre genios llamado Euler encontró una respuesta genial a esta pregunta... después de buscarla por 11 años!

Cuídense.