Hola, a veces necesitamos generar las particiones de un numero, una partición es una forma de escribir un numero entero positivo como la suma de otros numeros enteros positivos. Por ejemplo:
Para 3, las particiones serian:
1+1+1, 2+1, 3
Ahora, podemos necesitar los numeros que conforman las particiones o simplemente cuantas particiones tiene. Para este caso, explicare como obtener el numero de particiones con programacion dinamica y modificando este algoritmo se puede obtener que numeros conforman cada una de las particiones.
La pregunta es como llegamos a que las particiones de 3, en este caso, son esas. Bien, luego de ver varios ejemplos(el 4 y el 5) si ordenamos las particiones nos daremos cuenta de algo:
Particiones hasta 5:
N. 1:
1
N. 2:
11
2
N. 3:
1 11
1 2
3
N. 4:
1 111
2 11
2 2
3 1
4
N. 5:
1 1111
2 111
2 21
3 11
3 2
4 1
5
Si nos damos cuenta, las particiones del 3 tienen a las del 2. Las del 4 tienen las del 3 y las del 2 y asi sucesivamente.
En otras palabras, podemos formar un numero de la siguiente forma(para el 4 por ejemplo):
1 + alguna forma de escribir el tres (4-1)2 + alguna forma de escribir el dos (4-2)
3 + alguna forma de escribir el uno (4-3)
4 (solo hay una forma de escribir el numero con el mismo)
Entonces si quisieramos hacerlo para un numero y obtener todas las particiones hariamos algo como:
1+p(numero-1)
2+p(numero-2)
...
(n-1)+p(numero-(n-1)) es decir p(3) para el caso de las particiones de 4
n
p(numero) serian las particiones o el numero de particiones del numero
Y estas serian todas las particiones de n
El algoritmo para hacer esto en python seria:
numero = 5
particiones = [1] + [0] *numero
for i in xrange(1,numero+1):
for j in xrange(i, numero+1):
particiones[j] +=particiones[j-i]
#print(particiones)
print(particiones[numero])
La ejecucion de este programa daria lo siguiente:[1, 1, 1, 1, 1, 1]
[1, 1, 2, 2, 3, 3]
[1, 1, 2, 3, 4, 5]
[1, 1, 2, 3, 5, 6]
[1, 1, 2, 3, 5, 7]
y en cada iteracion sucede, tomamos un valor y anadimos las particiones del valor que falta para completar el numero.
particiones[j] = particiones que lleve + formas de hacer el valor que falta (j-i)
Podriamos modificar este algoritmo y en vez de solo sumar, agregar cada una de las particiones y asi obtendriamos los valores que conforman estas particiones
Nota: este problema esta relacionado con un problema muy conocido que consiste en saber de cuantas formas diferentes se puede devolver una cantidad de dinero usando solo las denominaciones dadas.
Nota2: una pregunta interesante es como hacer para que en las particiones un valor no aparezca mas de una vez, sin necesidad de validar luego de haber obtenido las particiones.
Espero les sirva!
