… o cómo aprendí a amar los generadores en Python y dejé de preocuparme.
En estos días mi trabajo en el doctorado involucra contar cuántos puntos con coordenadas enteras tienen ciertos “poliedros” en 12 dimensiones. Tales poliedros están determinados por las formas diferentes en que se puede descomponer un número como sumas ordenadas, es decir particiones. Así, dado que 6=3+1+1+1, entonces [3,1,1,1] es una partición de 6.
Las distintas particiones de n=6 son
[6] [5, 1] [4, 2] [4, 1, 1] [3, 2, 1] [3, 1, 1, 1] [2, 2, 2] [2, 2, 1, 1] [2, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1]
En la aplicación particular que estoy trabajando, únicamente nos importan particiones de longitud 3. Entonces de las anteriores sólo se considerarían
[4, 1, 1]
[3, 2, 1]
[2, 2, 2]
Como siempre es mejor usar la computadora para las tareas mecánicas, me propuse elaborar un programa en Python que genere particiones de un número entero.
El esquema básico es el siguiente:
- Recorrer todos los números n, n-1, n-2, .., 3, 2, 1 para ocupar la primera posición
- Una vez fija la primera posición k, el resto se genera “uniendo” esa primera posición con todas las particiones de n-k.
Por ejemplo, si n=6, y k=4 entonces todas las particiones que inician con 4 se obtienen de las particiones de 2: [2] y [1,1], dando como resultado [4,2] y [4,1,1], ambas mencionadas arriba.
En particular, una partición es una lista, y el resultado del programa debe ser una lista de listas. Finalmente, aunque en mi aplicación sólo es necesario calcular particiones de longitud 3, me conviene poder calcular particiones de cualquier otra longitud fija.
Bosquejo inicial
# coding=latin1 def particiones(n): if n==1: # Esto detiene la recursión, si n=1, la única partición es [1], # por lo que la lista de las particiones es [ [1] ] return [ [1] ] elif n<1: return [] # Por si acaso atrapar casos "raros". Si n=0, no hay particiones, regresar [] # de modo similar para n<0. listaparticiones=[] # incialmente no tenemos ninguna partición calculada for k in range(n,0,-1): # Aquí recorremos todos los valores k para el primer elemento cola= particiones(n-k) # generamos la lista de particiones de n-l for x in cola: # y para cada una de ellas... particion= [k] + x # la unimos con el primer elemento listaparticiones.append(particion) # y la agregamos a la lista return listaparticiones # al final devolvemos todas las que hayamos construido lista=particiones(5) # calcularemos las particiones de n=5... for p in particiones(5): # y luego las mostraremos print p
Todo listo, corremos y…
[4, 1]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 3, 1]
[1, 2, 1, 1]
[1, 1, 2, 1]
[1, 1, 1, 1, 1]
Se ha omitido [5] porque la recursión termina cuando n<0 la lista sobre la que se itera es vacía. Esto se soluciona cambiando
elif n<1:
return []
por
elif n<1:
return [ [] ]
Sin embargo, algo ha salido mal, porque [1,3,1] no es partición. El problema es que el esquema original no contempla que las “colas” que generan las particiones de n-k no pueden iniciar con un entero mayor que la “cabeza” k.
Otro problema menos evidente y mucho más interesante, es que se están efectuando muchísimas recursiones, en cada paso manteniendo en memoria listas muy grandes de particiones de forma innecesaria (por ejemplo, hay 200 000 particiones de n=50, y al efectuar la recursión fácilmente se usarán varios megabytes de memoria para algo tan sencillo). Además, se hace necesario almacenar la lista de particiones en una variable para poder recorrerla, como en:
lista=particiones(5)
for p in particiones(5):
print p
La solución a ésto es descartar el enfoque rudimentario de hacer recursiones sobre listas y usar generadores.
Generadores en python
Un generador es una forma conveniente de crear funciones que regresan valores pertenecientes a una lista sin tener que calcular toda la lista de antemano. En el ejemplo anterior, es necesario calcular TODA la lista de particiones
lista=particiones(5)
antes de poder mostrar siquiera la primera. Sería mucho más conveniente que particiones() diera cada una de ellas al necesitarlas, sin necesidad de calcularlas todas de antemano, lo cual se obtiene mediante el uso de generadores.
Otro uso de los generadores es devolver los elementos de una lista infinita, y como matemáticos esto es muy útil, sobre todo si se quiere modelar series y sucesiones.
Por ejemplo, queremos generar una lista de las primeras t aproximaciones a la suma 1 + (1/2) + (1/3) + … + (1/n). La función sería:
def armonica():
suma=0.0 # inicializamos valores
n=0.0
while True: # ciclo infinito!!
n=n+1 # aumentamos la variable
suma = suma + 1/n # calculamos la nueva suma
yield suma # regresamos el nuevo valor
El uso de yield en vez de return convierte a la función en un generador, que regresa sus valores de uno en uno en vez de todos al mismo tiempo.
Y el siguiente es un ejemplo de su uso:
t=6
z=armonica()
for j in range(t):
print z.next()
resultando en
1.0 # 1 1.5 # 1 + 1/2 1.83333333333 # 1 + 1/2 + 1/3 2.08333333333 # 1 + 1/2 + 1/3 + 1/4 2.28333333333 # 1 + 1/2 + 1/3 + 1/4 + 1/5 2.45 # 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6
Siendo clave la línea
print z.next()
en la que calcula el siguiente término, sin necesidad de recalcular los anteriores y sin necesidad de calcular los siguientes (al no saber cuántos se le pedirán).
Por ejemplo, si queremos generar todas las aproximaciones hasta que excedamos 3 podemos usar:
for x in armonica():
print x
if x >3: break
Este ejemplo es más ilustrativo, porque no sabemos ni siquiera cuántos elementos se calcularán, simplemente se calcula de uno en uno hasta obtener alguno que exceda 3. La línea for x in armonica(): está haciendo uso de que armonica() es un iterador, por lo que se puede recorrer de uno en uno como cuando se recorre range().
De vuelta al problema
Necesitamos entonces 2 cambios: usar generadores y establecer un tope (opcional) al elemento inicial, tope que es necesario para evitar obtener resultados del tipo [1, 3, 1, 1].
def particiones(n, tope=None): # tope es un parámetro opcional
if tope==None: tope=n # si no está presente, la cabeza de la partición puede ser
# tan grande como n mismo
if n==1:
yield [1] # dado que ya no regresamos una "lista de listas"
elif n<1: # sino sólo un elemento, ya no necesitamos los corchetes extra
yield []
else: # necesario pues a diferencia de return, la función no termina al
# al llegar a yield, sino que sólo se pausa
for k in range(min(n,tope),0,-1): # min(n,tope) impide que las cabezas sean mayores topes
for cola in particiones(n-k,tope=k): # y cada cabeza es tope de las subllamadas
particion= [k] + cola
yield particion
Notemos que ya no fue necesario usar variables auxiliares como listaparticiones y colas para almacenar las listas temporales, sino que el uso de generadores (yield) permite acceder a las funciones mismas como si fueran listas.
Usamos la función anterior como:
for x in particiones(5):
print x
Obteniendo:
[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]
O como en
for x in particiones(6,tope=4):
print x
que resulta en
[4, 2]
[4, 1, 1]
[3, 3]
[3, 2, 1]
[3, 1, 1, 1]
[2, 2, 2]
[2, 2, 1, 1]
[2, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
Las cuales son las particiones de 6 sin elementos mayores a 4.
Toques finales
Casi estamos listos, sólo falta ahora filtrar de forma opcional aquellas particiones que tengan una longitud dada. Añadiremos un nuevo parámetro auxiliar “partes” que dirá el número de partes en que se divide n:
def particiones(n, tope=None, partes=-1):
# sólo usaremos "partes" cuando sea positiva, por eso el valor inicial de -1
if tope==None: tope=n
if n==1:
yield [1]
elif n<1:
yield []
else:
for cabeza in range(min(n,tope),0,-1):
for cola in particiones(n-cabeza,tope=cabeza,partes=partes-1): # cada subllamada disminuye las partes en 1
particion= [cabeza] + cola
if (partes<0) or ((partes>0) and (len(particion)==partes) ): # cuando el número de partes no importa
# o coincide con el número de partes requerido
yield particion # devolver la partición
Dado que en cada etapa se filtran las particiones para devolver las que tienen el número de partes necesario, en las etapas más profundas de la recursión se regresan menos particiones y por tanto al construir las particiones totales al salir de las recursiones se hacen muchas menos concatenaciones, de modo que el programa corre mucho más rápido que si directamente se generaran todas y a la salida final se filtraran las que tienen el tamaño deseado.
El resultado de invocar a la función con
for x in particiones(6, partes=3):
print x
es:
[4, 1, 1]
[3, 2, 1]
[2, 2, 2]
Podemos incluso combinar los parámetros. Así, pedimos las particiones de 10 cuya primera entrada no exceda de 6 y que tengan 4 partes:
for x in particiones(10, partes=4, tope=6):
print x
obteniendo:
[6, 2, 1, 1]
[5, 3, 1, 1]
[5, 2, 2, 1]
[4, 4, 1, 1]
[4, 3, 2, 1]
[4, 2, 2, 2]
[3, 3, 3, 1]
[3, 3, 2, 2]
Y con eso damos por terminado el trabajo que queríamos.
Hola pro en que lenguaje esta el programa necesito uno que calcule las particiones de n numeros tu logica me hayudo pero aun no lo tengo ojala puedas darme una mano es para mañana viernes 5 de junio ojala puedas gracias
Es Python. Y calcula las partciones de “un número”. no sé qué quieras decir con las particiones de n números.