29. Permutaciones de n elementos

Determinar todas las posibles ordenaciones de n elementos sin repetición. Por ejemplo, para la lista [1,2,3] las posibles ordenaciones son:

Python [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

La forma más sencilla de resolver este problema es mediante una función recursiva que reduzca su complejidad. Por ejemplo, para el caso de arriba la lista de las permutaciones es: 1 seguido de cada una de las permutaciones de [2,3], 2 seguido de cada una de las permutaciones de [1,3] y 3 seguido de cada una de las permutaciones de [1,2].

Es decir, cada uno de los elementos se toma como el primer elemento y se concatena con el resultado de las permutaciones del resto de los elementos.

def permutaciones(l):
    '''Asume l lista de elementos.
       Devuelve una lista de permutaciones. Cada
       permutación es una lista como l pero con
       los elementos reordenados.'''
    if len(l) < 2:
        return [l]
    ret = []
    for i in l:
        ret += concat_elem_permutaciones(i, resto(l,i))
    return ret

def concat_elem_permutaciones(elem, l):
    '''Asume elem de cualquier tipo, l lista de elementos.
       Devuelve una lista de permutaciones de l pero con
       elem añadido a la cabeza.'''
    ret = []
    for i in permutaciones(l):
        ret.append([elem] + i)
    return ret

def resto(l, elem):
    '''Asume l lista, elem un elemento presente en l.
       Devuelve una lista con los mismos elementos
       salvo elem.'''
    r = l[:]
    r.remove(elem)
    return r
permutaciones([1,2,3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Se puede abreviar bastante usando comprensiones de lista:

def permutaciones(l):
    '''Asume l lista de elementos.
       Devuelve una lista de permutaciones. Cada
       permutación es una lista como l pero con
       los elementos reordenados.'''
    if len(l) < 2:
        return [l]
    return sum([concat_elem_permutaciones(i, resto(l,i)) for i in l ], [])

def concat_elem_permutaciones(elem, l):
    '''Asume elem de cualquier tipo, l lista de elementos.
       Devuelve una lista de permutaciones de l pero con
       elem añadido a la cabeza.'''
    return [[elem] + i for i in permutaciones(l)]

def resto(l, elem):
    '''Asume l lista, elem un elemento presente en l.
       Devuelve una lista con los mismos elementos
       salvo elem.'''
    return [x for x in l if x != elem]

29.1. Usando generadores

El problema está resuelto pero permíteme presentar otra posible solución.

La solución que hemos presentado arriba devuelve una lista con todas las posibles permutaciones. Como puedes imaginar esto puede llegar a ocupar mucho. Imagina que tenemos que calcular las permutaciones de 20 elementos. El resultado serían factorial(20) listas de 20 elementos. ¿Sabes cuánto es eso? Te lo diré en TB suponiendo que cada elemento ocupa solo un byte:

from math import factorial
round(20*factorial(20)/(1024**4))
44254230

Son 44 millones de TB. Ni siquiera cabría en el disco duro de tu ordenador. Los discos duros más grandes que se venden hoy en día son de 4TB. Necesitaríamos más de 10 millones de discos de 4TB.

Si queremos permutaciones de un número razonable de elementos es evidente que no podemos guardarlo en una lista. Tenemos que ir generando sobre la marcha. Para eso puede ayudarnos mucho una utilidad de Python, los generadores. Funcionan de forma parecida a los range. Cuando los intentamos recorrer van produciendo elementos. Veamos por ejemplo un generador para generar los n primeros cuadrados:

def cuadrados(n):
    '''Genera los n primeros cuadrados'''
    for i in range(n):
        yield i**2

La palabra clave yield produce un resultado parcial. Los detalles internos no es necesario conocerlos de momento. Vamos a intentar usarla:

cuadrados(10)
<generator object cuadrados at 0x00000080A040B150>

Le pasa los mismo que a los range. No nos muestra información útil pero podemos usarlo como si fuera una lista:

for i in cuadrados(10):
    print(i, end=' ')
0 1 4 9 16 25 36 49 64 81

Incluso podemos convertirlo en lista de la misma forma que un range. Lo interesante es que si no necesitamos convertirlo en lista no ocupa la memoria correspondiente a todos los elementos.

list(cuadrados(10))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Vamos a usar esta característica para generar permutaciones.

def permutaciones(l):
    if len(l) < 2:
        yield l[:]
        return
    for i in l:
        for j in permutaciones(resto(l,i)):
            yield [i] + j

def resto(l, elem):
    r = l[:]
    r.remove(elem)
    return r

Fíjate bien en que yield no es un return. Produce un resultado y se queda ahí hasta que se le pide otro resultado. Si ya no queremos seguir la ejecución del programa tenemos que usar return.

La forma de usarlo es similar a un range.

list(permutaciones([1,2,3]))
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Un generador no se llama como una función cualquiera. El generador se llama una vez para tener todos los resultados y después se itera sobre ellos usando next o un bucle for. Por ejemplo, veamos una forma de imprimir solo las 10 primeras permutaciones.

todas = permutaciones([1,2,3,4,5,6,7,8])
for i in range(10):
    print(next(todas))
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 8, 6]
[1, 2, 3, 4, 5, 8, 6, 7]
[1, 2, 3, 4, 5, 8, 7, 6]
[1, 2, 3, 4, 6, 5, 7, 8]
[1, 2, 3, 4, 6, 5, 8, 7]
[1, 2, 3, 4, 6, 7, 5, 8]
[1, 2, 3, 4, 6, 7, 8, 5]

De todas formas como puedes imaginar las permutaciones de una serie de elementos son muy útiles. Sería imperdonable que Python no tuviera ya una implementación en su biblioteca estándar. Está en itertools.

from itertools import permutations as permutaciones
list(permutaciones([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
Next Section - 30. Problema de las 8 damas