13 de junio de 2016

Combinaciones, permutaciones y otras diversiones

Imaginemos que estamos en una heladería y queremos un Tres Marías. Este delicioso postre se prepara con tres bolas de helado de diferentes sabores. La heladería cuenta con helado de los siguientes sabores: cereza, chocolate, fresa, nuez y vainilla. Con esta información, ¿qué elecciones de sabores tenemos para crear nuestro Tres Marías?      


La respuesta son las siguientes diez opciones:
  • Cereza, chocolate y fresa.
  • Cereza, chocolate y nuez.
  • Cereza, chocolate y vainilla.
  • Cereza, fresa y nuez.
  • Cereza, fresa y vainilla.
  • Cereza, nuez y vainilla.
  • Chocolate, fresa y nuez.
  • Chocolate, fresa y vainilla.
  • Chocolate, nuez y vainilla.
  • Fresa, nuez y vainilla.
Analicemos otro problema. Tenemos las siguientes tres letras: i, o, r. ¿Qué palabras podemos formar usando solamente esas tres letras?  Supongamos que no nos importa que algunas de las palabras formadas no existan en el idioma español. La respuesta son seis palabras:
  • ior
  • iro
  • oir
  • ori
  • rio
  • roi
El problema de los helados es un problema de combinaciones: deseamos determinar las formas de agrupar los elementos de un conjunto en donde no importa el orden en que se colocan dichos elementos. Un Tres Marías de chocolate, fresa y vainilla es igual a uno de fresa, vainilla y chocolate. Por otro lado, el problema de las letras es un problema de permutaciones: a diferencia de las combinaciones, aquí el orden sí nos interesa. No es lo mismo “rio” que “oir”.

Tradicionalmente, muchos libros de probabilidad y estadística comienzan con una descripción de cómo calcular el número de combinaciones o permutaciones de un conjunto. Sin embargo, si lo que nos interesa es obtener un listado con dichas combinaciones o permutaciones es muy probable que estos libros no expliquen la manera de hacerlo. Afortunadamente, con Python y un poco de ingenio podemos resolver este problema.

NOTA: Todo el código que aquí se presenta fue probado con Python 3.5.

Recordando al conjunto potencia

En nuestra entrada anterior discutimos cómo programar una función que calcula el conjunto potencia. Repetiremos aquí el código correspondiente por conveniencia, ya que estaremos haciendo uso de él más adelante.
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]

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)

Combinaciones

Se llama combinaciones de m elementos tomando n elementos a la vez (donde mn) a todas las agrupaciones posibles de tamaño n que pueden hacerse con los m elementos. Recordemos que no importa el orden de los elementos. Para esta discusión también supondremos que los elementos no se repiten.

Regresemos al problema original de las tres bolas de helado. Lo que queremos es encontrar todas las combinaciones que se pueden formar a partir de 5 sabores de helado tomando 3 sabores a la vez.

Primero veamos qué obtenemos cuando calculamos el conjunto potencia con los cinco sabores de helado:
>>> imprime_ordenado(
...     potencia(['cereza', 'chocolate', 'fresa', 
...               'nuez', 'vainilla']))
[]
['cereza']
['chocolate']
['fresa']
['nuez']
['vainilla']
['cereza', 'chocolate']
['cereza', 'fresa']
['cereza', 'nuez']
['cereza', 'vainilla']
['chocolate', 'fresa']
['chocolate', 'nuez']
['chocolate', 'vainilla']
['fresa', 'nuez']
['fresa', 'vainilla']
['nuez', 'vainilla']
['cereza', 'chocolate', 'fresa']
['cereza', 'chocolate', 'nuez']
['cereza', 'chocolate', 'vainilla']
['cereza', 'fresa', 'nuez']
['cereza', 'fresa', 'vainilla']
['cereza', 'nuez', 'vainilla']
['chocolate', 'fresa', 'nuez']
['chocolate', 'fresa', 'vainilla']
['chocolate', 'nuez', 'vainilla']
['fresa', 'nuez', 'vainilla']
['cereza', 'chocolate', 'fresa', 'nuez']
['cereza', 'chocolate', 'fresa', 'vainilla']
['cereza', 'chocolate', 'nuez', 'vainilla']
['cereza', 'fresa', 'nuez', 'vainilla']
['chocolate', 'fresa', 'nuez', 'vainilla']
['cereza', 'chocolate', 'fresa', 'nuez', 'vainilla']
El resultado consta de 32 subconjuntos (25=32). Si observamos cuidadosamente, hay exactamente 10 subconjuntos que son de cardinalidad 3. Esos 10 subconjuntos son precisamente las 10 diez combinaciones que se pueden formar a partir de un total de 5 elementos tomando 3 elementos a la vez. Sabiendo esto, podemos definir en una sola línea la función en Python que sirve para calcular combinaciones:
def combinaciones(c, n):
    """Calcula y devuelve una lista con todas las
       combinaciones posibles que se pueden hacer
       con los elementos contenidos en c tomando n
       elementos a la vez.
    """
    return [s for s in potencia(c) if len(s) == n]
Como podemos observar, aquí utilizamos una lista por comprensión, la cual se puede leer así: para cada subconjunto s que pertenece al resultado del conjunto potencia de c, conservar solo aquellos valores de s en donde su cardinalidad sea igual a n. Probando la función podemos ver que sí produce los resultados esperados:
>>> imprime_ordenado(
        combinaciones(['cereza', 'chocolate', 'fresa',
                       'nuez', 'vainilla'], 3))
['cereza', 'chocolate', 'fresa']
['cereza', 'chocolate', 'nuez']
['cereza', 'chocolate', 'vainilla']
['cereza', 'fresa', 'nuez']
['cereza', 'fresa', 'vainilla']
['cereza', 'nuez', 'vainilla']
['chocolate', 'fresa', 'nuez']
['chocolate', 'fresa', 'vainilla']
['chocolate', 'nuez', 'vainilla']
['fresa', 'nuez', 'vainilla']
El número de posibles combinaciones se denota \({}_m C_n \) y se calcula así: $$ {}_m C_n = \frac{m!}{n! \; (m - n)!} $$ En donde m es la cardinalidad del conjunto inicial y n es la cardinalidad de los subconjuntos que deseamos formar. El signo de admiración es la operación de factorial. Verificando nuestro ejemplo, donde m = 5 y n = 3, el resultado obtenido es el que hemos estado manejando: 5!/(3!*2!) = 120/(6*2) = 120/12 = 10.

La función en Python que calcula el número de combinaciones queda así:
from math import factorial

def numero_combinaciones(m, n):
    """Calcula y devuelve el número de combinaciones
       posibles que se pueden hacer con m elementos
       tomando n elementos a la vez.
    """
    return factorial(m) // (factorial(n) * factorial(m - n))
Podemos asegurarnos que las dos funciones que definimos, combinaciones() y numero_combinaciones(), son consistentes entre sí:
>>> len(combinaciones(range(20), 1))
20
>>> len(combinaciones(range(20), 1)) \
    == numero_combinaciones(20, 1)
True
>>> len(combinaciones(range(20), 10))
184756
>>> len(combinaciones(range(20), 10)) \
    == numero_combinaciones(20, 10)
True
>>> len(combinaciones(range(20), 20))
1
>>> len(combinaciones(range(20), 20)) \
    == numero_combinaciones(20, 20)
True
NOTA: El carácter de diagonal invertida (\) usado arriba indica que la instrucción continúa en la línea de abajo.

Permutaciones

Una permutación es la variación de la disposición u orden de los elementos de un conjunto.  Usaremos recursión para diseñar un algoritmo que permita permutar una lista. Hay que definir, entonces, dos cosas: el caso base y la llamada recursiva.

Caso base: El resultado de permutar un conjunto vacío es un conjunto que contiene al conjunto vacío.

Llamada recursiva: Nos interesa resolver una versión más simple del problema. Puede ser algo así: permutar el mismo conjunto de entrada pero quitándole un elemento, por ejemplo el primero. Analicemos la siguiente figura para comprender lo que deseamos lograr:


La llamada original es: permuta({x, y, z}). Vamos a hacer una llamada recursiva con el mismo conjunto pero sin su primer elemento. La llamada sería: permuta({y, z}). Por definición (o sea, por acto de fe) la llamada recursiva debe devolvernos lo siguiente: {{y, z}, {z, y}}. Ahora respondamos a la pregunta: ¿Qué se le debe hacer al resultado de la llamada recursiva permuta({y, z}) para convertirlo en el resultado esperado de la llamada original permuta({x, y, z})? El uso de los colores en la figura de arriba nos permiten responder a esta pregunta.

Tomemos el primer subconjunto del resultado de la llamada recursiva: {y, z}. A partir de éste, debemos insertar x (el elemento eliminado al momento de hacer la llamada recursiva) en cada posición posible de dicho subconjunto. Dado que hay dos elementos en el subconjunto, existen tres posibles posiciones de inserción: al inicio, en medio y al final. Los tres nuevos subconjuntos serían: {x, y, z}, {y, x, z} y {y, z, x}. Lo anterior hay que repetirlo para el segundo subconjunto de la llamada recursiva, en esta caso: {z, y}. Ahora obtendríamos: {x, z, y}, {z, x, y} y {z, y, x}. El proceso se repetiría de esta misma forma en caso de que el resultado de la llamada recursiva tuviera más subconjuntos. Todos los subconjuntos que generamos aquí conforman el resultado esperado de la llamada original.

Dividamos el problema en varias funciones de Python para simplificar su resolución.

La siguiente función crea una nueva lista a partir de una lista existente lst pero insertando el elemento x en la posición del índice i:
def inserta(x, lst, i):
    """Devuelve una nueva lista resultado de insertar
       x dentro de lst en la posición i.
    """
    return lst[:i] + [x] + lst[i:]
La expresión lst[:i] es una rebanada de la lista lst comenzando desde el inicio y hasta el elemento anterior al índice i. De manera similar, la expresión lst[i:] es una rebanada de la lista lst comenzando en el elemento del índice i y hasta el final de la lista. En medio de esas dos rebanadas creamos una nueva lista conteniendo a x. Por último, concatenamos todo en orden para crear la lista resultante.

NOTA:  Las listas de Python tienen un método insert() que podría parecerse mucho a nuestra función. Sin embargo nuestra versión no modifica la lista original, mientras que la de Python sí. Las funciones que definimos más adelante suponen que las inserciones no alteran la lista original.

Ejemplos de uso:
>>> inserta(42, [1, 2, 3], 0)
[42, 1, 2, 3]
>>> inserta(42, [1, 2, 3], 3)
[1, 2, 3, 42]
>>> inserta(42, [1, 2, 3], 1)
[1, 42, 2, 3]
La siguiente función nos genera una lista de listas con todas las posibles inserciones de un elemento:
def inserta_multiple(x, lst):
    """Devuelve una lista con el resultado de
       insertar x en todas las posiciones de lst.  
    """
    return [inserta(x, lst, i) for i in range(len(lst) + 1)]
La función range() produce los índices de todas las posiciones en las que deseamos hacer una inserción (desde 0 hasta el número de elementos de la lista original) y la lista por comprensión se encarga de llamar nuestra función inserta() para hacer el resto del trabajo.

La función inserta_multiple() puede usarse así:
>>> inserta_multiple(42, [])
[[42]]
>>> inserta_multiple(42, [1])
[[42, 1], [1, 42]]
>>> inserta_multiple(42, [1, 2])
[[42, 1, 2], [1, 42, 2], [1, 2, 42]]
>>> inserta_multiple(42, [1, 2, 3])
[[42, 1, 2, 3], [1, 42, 2, 3], [1, 2, 42, 3], [1, 2, 3, 42]]
Ahora sí, ya estamos en condiciones de implementar la función permuta():
def permuta(c):
    """Calcula y devuelve una lista con todas las
       permutaciones posibles que se pueden hacer
       con los elementos contenidos en c.
    """
    if len(c) == 0:
        return [[]]
    return sum([inserta_multiple(c[0], s)
                for s in permuta(c[1:])],
               [])
La expresión permuta(c[1:]) genera recursivamente todas las permutaciones de nuestro conjunto original c pero sin su primer elemento. Por cada subconjunto s devuelto por permuta(), la lista por comprensión realiza el inserta_multiple() con el primer elemento de c como argumento. Hay que tener en cuenta que esta lista por comprensión devuelve una lista de listas de listas. Esto quiere decir que hay un nivel en exceso de listas anidadas. Usamos la función sum() para concatenar las listas que están anidadas en la lista más externa y con ello nos queda el resultado que deseamos. El segundo parámetro de sum() es el valor con el que inicia la sumatoria, que por omisión es el número cero pues sum() se usa principalmente para sumar números. Sin embargo, si en su lugar se le manda una lista vacía como argumento la función sum() realiza una concatenación de listas, que es justamente lo que queremos.

Probemos permuta() con el segundo problema que propusimos al inicio de esta entrada:
¿Qué palabras podemos formar usando las letras i, o, r?
>>> imprime_ordenado(permuta(['i', 'o', 'r']))
['i', 'o', 'r']
['i', 'r', 'o']
['o', 'i', 'r']
['o', 'r', 'i']
['r', 'i', 'o']
['r', 'o', 'i']
Probando con otras entradas:
>>> permuta([])
[[]]
>>> permuta([1])
[[1]]
>>> permuta([1, 2])
[[1, 2], [2, 1]]
>>> imprime_ordenado(permuta([1, 2, 3]))
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
>>> imprime_ordenado(permuta([1, 2, 3, 4]))
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]
El número de permutaciones que se pueden obtener para un conjunto de cardinalidad n es: n!. Esto lo podemos verificar con el siguiente código:
>>> from math import factorial
>>> len(permuta(range(3)))
6
>>> len(permuta(range(3))) == factorial(3)
True
>>> len(permuta([]))
1
>>> len(permuta([])) == factorial(0)
True
>>> len(permuta(range(1)))
1
>>> len(permuta(range(1))) == factorial(1)
True
>>> len(permuta(range(5)))
120
>>> len(permuta(range(5))) == factorial(5)
True
>>> len(permuta(range(8)))
40320
>>> len(permuta(range(8))) == factorial(8)
True
En ocasiones puede resultar deseable calcular las permutaciones de un conjunto pero tomando solamente n elementos a la vez. Para ello podemos recurrir a la función combinaciones() junto con permuta():
def permutaciones(c, n):
    """Calcula y devuelve una lista con todas las
       permutaciones posibles que se pueden hacer
       con los elementos contenidos en c tomando n
       elementos a la vez.
    """
    return sum([permuta(s)
                for s in combinaciones(c, n)],
               [])
En este código usamos una lista por comprensión para calcular todas las combinaciones de c tomando n elementos a la vez, y luego permutar cada subconjunto obtenido. Finalmente concatenamos con sum() todas las listas con las permutaciones resultantes.

Ejemplo de uso:
>>> permutaciones([1, 2, 3], 0)
[[]]
>>> permutaciones([1, 2, 3], 1)
[[1], [2], [3]]
>>> permutaciones([1, 2, 3], 2)
[[1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]]
>>> imprime_ordenado(permutaciones([1, 2, 3, 4], 3))
[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]
Si m es la cardinalidad del conjunto original y vamos a formar grupos tomando n elementos a la vez, entonces el número de permutaciones posibles se denota \({}_m P_n\), y su fórmula es: $$ {}_m P_n = \frac{m!}{(m - n)!} $$ La función en Python que realiza este cálculo es:
def numero_permutaciones(m, n):
    """Calcula y devuelve el número de permutaciones
       posibles que se pueden hacer con m elementos
       tomando n elementos a la vez.
    """
    return factorial(m) // factorial(m - n)
Ahora verifiquemos si numero_permutaciones() es consistente con lo que permutaciones() nos devuelve:
>>> len(permutaciones(range(10), 0))
1
>>> len(permutaciones(range(10), 0)) \
    == numero_permutaciones(10, 0)
True
>>> len(permutaciones(range(20), 1))
20
>>> len(permutaciones(range(20), 1)) \
    == numero_permutaciones(20, 1)
True
>>> len(permutaciones(range(20), 4))
116280
>>> len(permutaciones(range(20), 4)) \
    == numero_permutaciones(20, 4)
True

Conclusión

El conjunto potencia y las listas por comprensión son nuestros mejores amigos para divertirnos diseñando algoritmos que generan combinaciones y permutaciones.



Finalmente, vale la pena comentar que el módulo itertools, disponible tanto en Python 2 como en Python 3, proporciona toda la funcionalidad que describimos aquí (y mucha más) en forma de generadores combinatorios. Sugiero utilizar dicho módulo si se tiene interés de obtener combinaciones y/o permutaciones sin tener que conocer los detalles de su implementación:
>>> from itertools import combinations, permutations
>>> list(combinations([1, 2, 3, 4], 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
>>> list(permutations([1, 2, 3, 4], 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), 
(1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), 
(2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), 
(3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), 
(4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]

11 de junio de 2016

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: 2n, 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.