Potenciando conjuntos

En nuestra entrada anterior conocimos lo que son las listas por comprensión y pudimos ver algunos ejemplos sencillos de cómo utilizarlas en Python. En esta entrada veremos un ejemplo más sofisticado de este tema: el conjunto potencia.

Portada de la sexta edición del libro
“Fundamentos de Matemáticas”
escrito por Juan Silva y Adriana Lazo.
Editorial Limusa, 2003.

Definición de conjunto potencia tal como
aparece en el texto de Silva y Lazo.

El conjunto potencia es un concepto matemático que recuerdo haber aprendido cuando estudiaba el tema de lógica y conjuntos en la preparatoria, por ahí de a mediados de la década de los años ochenta. Si no me falla la memoria, fue en el libro de “Fundamentos de Matemáticas” de Silva y Lazo donde lo vi por primera vez. Sin embargo no fue sino hasta algunos años después que me detuve a pensar cómo es que se podría programar el conjunto potencia en un lenguaje de programación. Esto fue a raíz de un taller sobre el lenguaje de programación Scheme (un dialecto del lenguaje Lisp) al que asistí en la Conferencia Latinoamericana de Informática (CLEI) de 1994 en México, impartido por el Dr. Daniel P. Friedman.

Friedman es profesor e investigador de ciencia de la computación en la Universidad de Indiana. Su principal área de interés es la teoría y aplicación de los lenguajes de programación. Es coautor de varios libros, de los cuales destacan principalmente dos: “The Little Schemer” que escribió junto con Matthias Felleisen, y “Essentials of Programming Languages” que escribió con Mitchell Wand y Christopher Haynes.

El profesor Daniel Paul Friedman.

Portada de la cuarta edición del libro
“The Little Schemer” escrito por
Daniel Friedman y Matthias Felleisen,
Editorial The MIT Press, 1995.

En el taller al que hago alusión, Friedman explicó la función map de Scheme y mostró cómo utilizarla para implementar en seis líneas de código una función recursiva que calculaba el conjunto potencia. La sencillez y elegancia de dicha implementación me deslumbró. En casi una década de programar cotidianamente en lenguajes como Basic, Pascal y C++, nunca había visto algo que se le pareciera.

El código de Scheme que presentó Friendman era algo así:

(define potencia 
  (λ (c)
    (if (null? c)
        '(())
        (let ((r (potencia (cdr c))))
          (append r (map (λ (s) (cons (car c) s)) r))))))

El código anterior puede resultar bastante críptico para quien nunca ha programado en Lisp, sobre todo por el uso aparentemente excesivo de paréntesis (Lisp es el acrónimo de: List Processing [procesamiento de listas], aunque algunas personas dicen que debería significar algo así como: Lost In a Sea of Parenthesis [Perdido en un mar de paréntesis]). Sin embargo esas seis líneas están repletas de conceptos poderosos que son aplicables en otros lenguajes de programación (incluyendo Python).

Lo más importante a recalcar aquí es que la función map de Scheme puede ser emulada directamente en Python a través de listas por comprensión (de hecho, Python también cuenta con la función map(), pero en general son más fáciles se usar las listas por comprensión). Así pues, presento a continuación, usando Python, el razonamiento lógico detrás del código que en su momento me impresionó tan positivamente.

NOTA: Todo el código que se presenta posteriormente fue elaborado para Python 3.5.

Definición matemática

Dado un conjunto C, el conjunto potencia de C es otro conjunto formado exclusivamente por todos los subconjuntos de C.

Por ejemplo, si C = {x, y, z}, el conjunto potencia de C, representado como ℘(C), es: {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}. Vale la pena notar que el conjunto resultante incluye tanto al conjunto vacío {} como al conjunto original C.

Como segundo ejemplo, supongamos que tenemos cuatro monedas con los siguientes valores: 1 peso, 2 pesos, 5 pesos y 10 pesos. ¿De qué maneras distintas podemos combinarlas y qué valor monetario obtenemos en cada caso? Resolviendo con el conjunto potencia:

• {} = 0 pesos
• {1} = 1 peso
• {2} = 2 pesos
• {1, 2} = 3 pesos
• {5} = 5 pesos
• {1, 5} = 6 pesos
• {2, 5} = 7 pesos
• {1, 2, 5} = 8 pesos
• {10} = 10 pesos
• {1, 10} = 11 pesos
• {2, 10} = 12 pesos
• {1, 2, 10} = 13 pesos
• {5, 10} = 15 pesos
• {1, 5, 10} = 16 pesos
• {2, 5, 10} = 17 pesos
• {1, 2, 5, 10} = 18 pesos

Implementación en Python

Python cuenta con un tipo de dato Set, sin embargo para lo que queremos hacer aquí resulta más adecuado usar listas convencionales para representar conjuntos. Así pues, la lista vacía [] representa un conjunto vacío y la lista [1, 2, 3] representa un conjunto de tres elementos.

Definamos un algoritmo recursivo para calcular el conjunto potencia. Como en cualquier procedimiento recursivo, debemos definir dos cosas:

1. El caso base.
2. La llamada recursiva. 

El caso base es bastante sencillo: el conjunto potencia de un conjunto vacío es un conjunto que contiene al conjunto vacío. Es decir, ℘({}) = {{}}. El código de Python correspondiente sería el siguiente (donde c es el parámetro de la función que contendrá el conjunto de entrada):

if len(c) == 0:
    return [[]]

Hay que notar que el valor devuelto no es una lista vacía sino una lista que contiene a la lista vacía.

La llamada recursiva es más elaborada. Para empezar, es importante que dicha llamada corresponda a una versión más simple del problema siendo resuelto. Por ejemplo, si estamos resolviendo ℘({x, y, z}), entonces la llamada recursiva puede involucrar calcular ℘({x, y}), en donde el nuevo problema es más simple dado que consiste en calcular el conjunto potencia para un conjunto con un elemento menos. Al quitar un elemento nos estamos acercando más al caso base, lo cual es indispensable pues debemos tener la certeza de que la función termina en algún momento. El código de Python sería:

r = potencia(c[:-1])

La expresión c[:-1] obtiene una rebanada (slice) de la lista c comenzando implícitamente en el índice 0 (el índice del primer de elemento la lista) y hasta un elemento antes del índice -1 (el índice del último elemento de la lista). Esto efectivamente devuelve una copia de la lista c pero sin su último elemento. El resultado de la llamada recursiva queda en la variable r, la cual usaremos más adelante.

Veamos el siguiente esquema para determinar lo que sigue:

Esta figura muestra que la llamada recursiva ℘({x, y}) devuelve el conjunto {{}, {x}, {y}, {x, y}}. Por definición eso es lo que debe devolver la función conjunto potencia cuando recibe {x, y} como entrada. Aquí debemos suponer (algunos dirían: “como acto de fe”) que la llamada recursiva efectivamente regresa el valor correcto. Lo que resta ahora es responder a la siguiente pregunta: ¿Qué debo hacerle al resultado de la llamada recursiva ℘({x, y}) para convertirlo en el resultado esperado de la llamada original ℘({x, y, z})?

Hay tres cosas que podemos notar en la figura:

1. El resultado de ℘({x, y, z}) tiene el doble de elementos que el resultado de  ℘({x, y}). 
2. La primera mitad del resultado de ℘({x, y, z}) está compuesta exactamente de los mismos elementos del resultado de ℘({x, y}).
3. La segunda mitad del resultado de ℘({x, y, z}) está compuesta por los mismos elementos del resultado de ℘({x, y}) pero añadiendo al final de cada subconjunto el elemento z, que fue el que eliminamos al momento de hacer la llamada recursiva.

Podemos plantear lo anterior en Python así:

return r + [s + [c[-1]] for s in r]

Recordemos que r almacena la lista obtenida como resultado de la llamada recursiva. La expresión [... for s in r] es una lista por comprensión que permite procesar cada subconjunto s contenido en el conjunto r. La expresión s + [c[-1]] dentro de la lista por comprensión añade el último elemento del conjunto c (el elemento del índice -1) a cada subconjunto s. Finalmente, la expresión completa r + [...] concatena las dos mitades del resultado descritas en los puntos 2 y 3 de arriba.

El código completo quedaría así:

def potencia(c):
    """Calcula y devuelve el conjunto potencia del 
       conjunto c.
    """
    if len(c) == 0:
        return [[]]
    r = potencia(c[:-1])
    return r + [s + [c[-1]] for s in r]

Probando el código desde el shell de Python:

>>> potencia([])
[[]]
>>> potencia([1])
[[], [1]]
>>> potencia([1, 2])
[[], [1], [2], [1, 2]]

Obteniendo las soluciones de los problemas que originalmente planteamos en la sección anterior:

>>> potencia(['x', 'y', 'z'])
[[], ['x'], ['y'], ['x', 'y'], ['z'], ['x', 'z'], 
['y', 'z'], ['x', 'y', 'z']]
>>> for t in potencia([1, 2, 5, 10]): 
...     print('{0:13} = ${1:2d}'.format(t, sum(t)))
...
[]            = $ 0
[1]           = $ 1
[2]           = $ 2
[1, 2]        = $ 3
[5]           = $ 5
[1, 5]        = $ 6
[2, 5]        = $ 7
[1, 2, 5]     = $ 8
[10]          = $10
[1, 10]       = $11
[2, 10]       = $12
[1, 2, 10]    = $13
[5, 10]       = $15
[1, 5, 10]    = $16
[2, 5, 10]    = $17
[1, 2, 5, 10] = $18

Cardinalidad del conjunto potencia

La cardinalidad de un conjunto C es el número de elementos que lo conforman, y se denota así: |C|. En Python usamos la función len() para determinar el número de elementos que tiene una lista.

Como vimos en nuestra implementación del conjunto potencia, el caso base devuelve el conjunto {{}}, el cual tiene una cardinalidad igual a 1. En cualquier otro caso se devuelve un conjunto cuya cardinalidad es el doble del resultado de su correspondiente llamada recursiva. En otras palabras, la cardinalidad del conjunto potencia de un conjunto C, denotado como |℘(C)|, es: 2ⁿ, donde n = |C|. Podemos verificar que nuestra función potencia() cumple con esta fórmula:

>>> len(potencia([]))
1
>>> len(potencia([])) == 2 ** 0
True
>>> len(potencia(range(4)))
16
>>> len(potencia(range(4))) == 2 ** 4
True
>>> len(potencia(range(20)))
1048576
>>> len(potencia(range(20))) == 2 ** 20
True

Recordemos que x ** n en Python significa elevar x al exponente n.

Imprimiendo bonito el resultado

El algoritmo que implementamos para calcular el conjunto potencia devuelve una lista de listas que, a primera vista, aparenta no tener orden alguno. Afortunadamente es sencillo definir una función que permita imprimir los elementos de nuestra lista resultante ordenada de manera más conveniente:

def imprime_ordenado(c):
    """Imprime en la salida estándar todos los
       subconjuntos del conjunto c (una lista de
       listas) ordenados primero por tamaño y
       luego lexicográficamente. Cada subconjunto
       se imprime en su propia línea. Los
       elementos de los subconjuntos deben ser
       comparables entre sí, de otra forma puede
       ocurrir un TypeError.
    """
    for e in sorted(c, key=lambda s: (len(s), s)):
        print(e)

La función imprime_ordenado() hace uso a su vez de la función sorted(), la cual está predefinida en Python. A sorted() le mandamos como argumentos la lista a ordenar c (un conjunto de conjuntos) y un objeto lambda (función anónima) que se usa para calcular la llave (key) a utilizar al momento de realizar las comparaciones. En este caso nuestra función anónima crea una tupla con el tamaño de cada sublista s siendo comparada y el valor propio de s. Con esto garantizamos efectivamente que primero se compara la cardinalidad de cada subconjunto y en caso de un empate se compara entonces usando su valor. Por ejemplo, la lista [2, 3] se considera menor que [1, 2, 3] por ser más pequeña. Sin embargo, la lista [2, 3] es menor que la lista [2, 4], ya que son del mismo tamaño pero lexicográficamente (según el orden de diccionario) la primera lista debe ir antes que la segunda.

Ahora ya podemos usar la función imprime_ordenado() de la siguiente manera para producir un resultado más agradable a la vista:

>>> imprime_ordenado(potencia([1, 2, 3, 4]))
[]
[1]
[2]
[3]
[4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]

Conclusión

En esta entrada diseñamos un algoritmo recursivo para calcular el conjunto potencia. Utilizamos una lista por comprensión para simplificar la manera de procesar listas anidadas dentro una lista más grande. En la próxima entrada del blog de EduPython veremos más aplicaciones de las listas por comprensión y descubriremos que el conjunto potencia se puede utilizar también para generar combinaciones y permutaciones.