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:
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'":
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.