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.