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 m ≥ n) 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 (2⁵=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)]