Cómo generar todas las permutaciones de una lista en Python

Puedes generar permutaciones de una lista con la biblioteca estándar de Python o elegir un algoritmo recursivo o iterativo si necesitas personalizar el proceso. Una permutación es una ordenación de los elementos seleccionados; a diferencia de una combinación, el orden sí importa. La cantidad de resultados crece de forma factorial, por lo que generar todas las ordenaciones solo resulta práctico con entradas moderadas.

Usar itertools.permutations para generar todas las permutaciones de una lista en Python

Para la mayoría de los casos, conviene usar itertools.permutations. La función devuelve un iterador de tuplas, lo que permite procesar los resultados uno por uno sin crear una lista de inmediato. De forma predeterminada, r es la longitud de la entrada, así que cada resultado utiliza todos sus elementos. En el ejemplo, r=2 selecciona pares ordenados y el bucle recorre las longitudes de uno a tres.

Con la lista [1, 2, 3], el programa muestra:

from itertools import permutations

data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
    print(r, list(permutations(data, r)))

full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

El argumento r establece cuántos elementos tendrá cada tupla. Para generar todas las longitudes no vacías, llama a la función una vez por cada valor de r, desde 1 hasta la longitud de la entrada, como en el ejemplo. itertools.permutations trata los elementos según su posición: si un valor aparece más de una vez en la entrada, algunas tuplas resultantes pueden repetirse.

Consulta la documentación oficial de itertools para ver la firma completa de la función y su comportamiento.

Generar permutaciones con una función recursiva

Una solución recursiva elige cada elemento por turno y lo coloca delante de cada permutación de los elementos restantes. El caso base devuelve una lista que contiene una única ordenación vacía; así, la construcción funciona con entradas de cualquier longitud, incluso cero. Esta versión devuelve listas en lugar de tuplas y resulta útil para estudiar o personalizar el proceso.

def permute(data):
    if not data:
        return [[]]

    result = []
    for index, item in enumerate(data):
        remaining = data[:index] + data[index + 1:]
        for tail in permute(remaining):
            result.append([item] + tail)
    return result

print(permute([1, 2, 3]))

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

Cada llamada recursiva elimina una posición, por lo que la entrada restante se reduce hasta llegar al caso base. Los valores repetidos en posiciones distintas también pueden producir listas duplicadas. Esta implementación almacena todos los resultados y realiza muchas llamadas recursivas, así que es más apropiada para aprender o para entradas pequeñas; si no necesitas una construcción personalizada, usa el iterador de la biblioteca estándar.

Enfoque iterativo para generar permutaciones

También puedes construir los resultados insertando cada elemento nuevo en todas las posiciones de las ordenaciones parciales que ya tienes. La lista comienza con una ordenación vacía y, en cada paso, crece por un factor igual a la longitud de la entrada procesada. Este método evita las llamadas recursivas, pero sigue almacenando todos los resultados.

def iterative_permute(data):
    results = [[]]
    for item in data:
        next_results = []
        for ordering in results:
            for index in range(len(ordering) + 1):
                next_results.append(ordering[:index] + [item] + ordering[index:])
        results = next_results
    return results

print(iterative_permute([1, 2, 3]))

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

El orden de inserción determina el orden en que este método devuelve los resultados, pero no cambia qué permutaciones genera. Elígelo cuando la construcción paso a paso se ajuste a tu tarea y ten en cuenta la memoria necesaria para conservar el resultado completo.

Conclusión

Usa itertools.permutations para obtener un iterador conciso y perezoso, y establece r cuando necesites una longitud concreta. Recurre a la recursión o a la inserción iterativa si quieres personalizar la construcción o aprender cómo funciona. Una lista de longitud n tiene n! permutaciones completas cuando sus posiciones se consideran distintas, por lo que tanto el tiempo de procesamiento como el espacio necesario para materializar el resultado crecen rápidamente. Con entradas grandes, procesa el iterador según lo necesites o genera solo las longitudes y selecciones pertinentes.

Preguntas frecuentes

1. ¿Qué es una permutación?
   Es una selección ordenada de elementos. Por ejemplo, [1, 2] y [2, 1] son permutaciones distintas porque cambia el orden.

2. ¿Cómo funciona itertools.permutations?
   Genera tuplas de longitud r a partir del iterable de entrada. Si omites r, usa la longitud completa de la entrada. La función produce los resultados de forma perezosa, pero convertir el iterador en una lista almacena todos los resultados.

3. ¿Qué ocurre si la entrada contiene valores duplicados?
   La función considera las posiciones, no si los valores son iguales. Por eso, los valores repetidos en la entrada pueden producir tuplas idénticas. Si sus elementos admiten hash, convertir todos los resultados en un conjunto puede eliminar las tuplas repetidas después de generarlas, pero no evita ese trabajo. Para evitarlo, usa un algoritmo que omita las opciones iguales en cada paso.

4. ¿Cuántas permutaciones hay?
   Para n posiciones distintas, hay n! permutaciones de longitud completa. Si eliges solo r posiciones, la cantidad es n! / (n - r)!.

5. ¿Qué tan grande puede ser la entrada?
   No existe un límite único que sirva para todos los equipos y tareas. El crecimiento factorial puede hacer que procesar incluso una entrada moderada resulte costoso, y almacenar todos los resultados requiere mucha memoria. Si no necesitas todos los resultados de longitud completa a la vez, prefiere la iteración perezosa o un valor menor de r.