8.8. Partición y composición de enteros.

La partición de un número entero es la forma de descomponerlo en forma de suma, con uno o más sumandos positivos (a los que se les conoce como partes). La permutación de sumandos se considera la misma partición. Por ejemplo, el número 4 tiene particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

A la función que da como resultado la cantidad de particiones para un número n se le conoce como función partición y está representado por P(n). Por convención, P(0) = 1 y P(n) = 0 para n < 0.

Esta función es muy similar a la del cambio, sólo que podemos considerar que tenemos monedas de denominaciones entre 1 y n. Entonces, utilizando la función P(n, k) como la función partición utilizando particiones menores o iguales a k, podemos calcular P(n, k) obteniendo primero P(n, k-1) y sumándole P(nk, k).

Cuando a la permutación de sumandos se les considerar un resultado distinto, se le conoce como composición de enteros. Y cuando se permite utilizar el número cero en la composición, a veces se le llama composición débil. Por ejemplo, el número 4 tiene 8 composiciones: 4, 3+1, 2+2, 2+1+1, 1+3, 1+2+1, 1+1+2, 1+1+1+1. La cantidad de composiciones para un número está dada por 2n-1 para n ≥ 1; y al igual que con la partición, por convención existe una composición para el cero y ninguna para números negativos.


Problema ejemplo


Pedro el Enamorado

Problema
Pedro tiene monedas de cualquier valor entero positivo en una cantidad ilimitada. Quiere comprarle a su novia un pastel que cuesta n rublos. Encuentra las distintas formas en que puede pagar el pastel.

Entrada
Consiste en un entero n < 100.

Salida
La cantidad de formas p(n).

Solución: Utilizamos un algoritmo prácticamente igual al del problema anterior, sólo debemos ajustar la relación a la que acabamos de obtener.


Código


La única variable que vamos a utilizar es n, que es el precio del pastel (líneas 1 y 2).

En la función particion calculamos P(n) (líneas 4 a 14). Las variables i y j las utilizamos en los ciclos, y el arreglo p lo usamos para guardar los valores de la función partición. Inicializamos todos los valores de p a cero, con excepción del valor en la casilla cero que la igualamos a uno (líneas 8 y 9). Después utilizamos la relación que obtuvimos para ir calculando los valores de p (donde i toma los valores de kj los de n). Terminamos devolviendo las formas en que podemos partir n.

En la parte principal del código (líneas 16 a 19), simplemente leemos n y escribimos P(n).


Caso ejemplo

Entrada: 7
Desarrollo:            p[]
1: 1  1  1  1  1  1  1
2: 1  2  2  3  3  4  4
3: 1  2  3  4  5  7  8
4: 1  2  3  5  6  9 11
5: 1  2  3  5  7 10 13
6: 1  2  3  5  7 11 14
7: 1  2  3  5  7 11 15
Salida: 15


Otro enfoque: función generadora

Podemos obtener un algoritmo más eficiente utilizando la siguiente función generadora, atribuida a Euler:

Cuando el valor de  se vuelve menor que uno, entonces todos los valores P son cero. El valor de i a partir del cual P devuelve cero es:

Cuyas soluciones son:

Como i sólo toma valores enteros positivos, tenemos:

Como dato interesante, la función está relacionada con los números pentagonales, los cuales son de la forma .


El uso de las variables es el mismo que en el problema anterior, y añadimos las variables x e y para guardar valores temporales. El arreglo p tiene una casilla más (la menos uno) para poder manejar valores negativos. Empezamos inicializando las variables (líneas 5 y 6). Entre las líneas 7 y 16 calculamos el valor de P(n) de acuerdo a al función anterior. Las únicas consideraciones que debemos tomar son que el valor hasta que llega j es ligeramente mayor al que calculamos (línea 8) y que para valores negativos P(n) devuelve el mismo resultado (líneas 12 y 13).

Al utilizar esta fórmula, hemos mejorado el tiempo de ejecución de O(n2) a O(n1.5).


Códigos en C




Tiempo de ejecución

Lenguaje Fecha Tiempos [s] Memoria [Kb]
Ejecución Mejor Mediana Peor
Pascal 28-Abr-2006 0.010 0.010 - - 100
C 28-Abr-2006 0.010 111
Pascal 28-Abr-2006 0.010 195
C 28-Abr-2006 0.010 198


Otros problemas

Project Euler:





© Pier Paolo Guillen Hernandez
World of πer