Binary Coffee

Generando permutaciones en Python

algorithms python

Backtracking

Para generar las permutaciones del conjunto A = [1, 2, ..., N] para un N dado usaremos un algoritmo recursivo de tipo backtraking. La idea es tener un arreglo p donde se ir谩 construyendo la permutaci贸n, en todo momento desde la posici贸n 0 hasta la posici贸n i (0 <= i < N) se tendr谩n ubicados i + 1 elementos distintos del conjunto A, entonces recursivamente se intentar谩n ubicar a partir de la posici贸n i + 1 en p los restantes elementos no posicionados todav铆a, esto se hace iterando por todos los elementos candidatos y ubicando uno a la vez en la posici贸n correspondiente e invocando recursivamente para continuar construyendo la permutaci贸n sobre p. Cuando i sea igual a N entonces tenemos una permutaci贸n y la guardamos como una tupla. Luego de la llamada recursiva se debe quitar el 煤ltimo elemento ubicado en p para que en llamadas siguientes pueda ser usado para ubicarlo en otras posiciones durante el algoritmo de backtraking. Ve谩moslo en un ejemplo para N = 3:

A = [1, 2, 3]

backtracking(0, [0, 0, 0])
  backtracking(1, [1, 0, 0])
    backtracking(2, [1, 2, 0])
      backtracking(3, [1, 2, 3]) almacenamos la permutaci贸n (1, 2, 3)
    backtracking(2, [1, 2, 0])
  backtracking(1, [1, 0, 0])
    backtracking(2, [1, 3, 0])
      backtracking(3, [1, 3, 2]) almacenamos la permutaci贸n (1, 3, 2)
    backtracking(2, [1, 3, 0])
  backtracking(1, [1, 0, 0])
backtracking(0, [0, 0, 0])
  backtracking(1, [2, 0, 0])
    backtracking(2, [2, 1, 0])
      backtracking(3, [2, 1, 3]) almacenamos la permutaci贸n (2, 1, 3)
.... as铆 sucesivamente hasta                                    .
      .                                                         .
      backtracking(3, [3, 2, 1]) almacenamos la permutaci贸n (3, 2, 1)

Implementaci贸n en permutations.py:

def recursive_permutations(p, i, n, res):
    if i == n:
        res.append(tuple(p))
    else:
        for x in range(1, n + 1):
            if x not in p:
                p[i] = x
                recursive_permutations(p, i + 1, n, res)
                p[i] = 0


def permutations(n):
    """
    Returns a list with all permutations of [1, 2, ..., n].

    >>> permutations(1)
    [(1,)]
    >>> permutations(2)
    [(1, 2), (2, 1)]
    >>> permutations(3)
    [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
    """
    p = [0] * n
    res = []
    recursive_permutations(p, 0, n, res)
    return res

Como ven la funci贸n permutations() recibe n y retorna una lista con las n! permutaciones, adem谩s tiene un doctest que puede ejecuarse por la consola as铆 python -m doctest -v permutations.py o si usamos PyCharm:

Usando Itertools

Python tiene un m贸dulo que permite generar varias secuencias combinatorias, en particular las permutaciones. Veamos:

import itertools

for p in itertools.permutations(range(1, 4)):
    print(p)

Salida:

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Hagamos un m贸dulo de prueba (unittest) para comprobar nuestra primera implementaci贸n contra la salida de esta funci贸n del m煤dulo itertools:

import permutations
import itertools
import unittest


class TestPermutations(unittest.TestCase):

    def test_permutations(self):
        for n in range(0, 8):
            actual = permutations.permutations(n)
            expected = list(itertools.permutations(range(1, n + 1)))
            self.assertEqual(actual, expected)

Luego corri茅ndolo con PyCharm es tan simple como clic derecho arriba del m贸dulo y ejecutar "Run 'Unittest in permutations_tests.py'":

Conclusiones

Vimos como generar permutaciones por backtracking y por medio del m贸dulo itertools. Adem谩s usamos pruebas unitarias para probar las implementaciones. Te invito a que busques problemas cl谩sicos donde puedeas poner en pr谩ctica las permutaciones, por ejemplo el problema de ubicar N reinas en un tablero de NxN de modo que ning煤n par se ataque.

Opiniones