magister

Generando particiones

In matemáticas, programación, python on mayo 27, 2008 at 9:15 pm

… 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:

  1. Recorrer todos los números n, n-1, n-2, .., 3, 2, 1  para ocupar la primera posición
  2. 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.

Anuncios
  1. 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

  2. Es Python. Y calcula las partciones de “un número”. no sé qué quieras decir con las particiones de n números.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: