Generando permutaciones en 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.