Como gerar todas as permutações de uma lista em Python

Use a biblioteca padrão do Python para gerar permutações de uma lista ou escolha um algoritmo recursivo ou iterativo quando precisar personalizar o processo. Uma permutação é uma ordenação de elementos selecionados; ao contrário de uma combinação, a ordem importa. A quantidade de resultados cresce de forma fatorial, portanto gerar todas as ordenações só é prático para entradas modestas.

Usando a biblioteca itertools

Na maioria dos casos, use itertools.permutations. A função retorna um iterador de tuplas, permitindo processar os resultados um de cada vez em vez de criar uma lista imediatamente. Por padrão, r corresponde ao comprimento da entrada, então cada resultado usa todos os elementos. No exemplo, r=2 seleciona pares ordenados, e o laço percorre cada comprimento de um a três.

Para a lista [1, 2, 3], o programa imprime:

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)]

O argumento r define a quantidade de itens em cada tupla. Para gerar todos os comprimentos não vazios, chame a função uma vez para cada valor de r, de 1 até o comprimento da entrada, como no exemplo. itertools.permutations considera os elementos por posição: se um valor aparece mais de uma vez na entrada, algumas tuplas resultantes podem se repetir.

Consulte a documentação oficial de itertools para ver a assinatura completa e o comportamento da função.

Função recursiva para permutações

Uma solução recursiva escolhe cada item por vez e o coloca antes de cada permutação dos itens restantes. O caso-base retorna uma lista contendo uma ordenação vazia; assim, a construção funciona para qualquer comprimento de entrada, inclusive zero. Esta versão retorna listas em vez de tuplas e é útil para estudar ou personalizar a construção.

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 chamada recursiva remove uma posição, reduzindo a entrada até alcançar o caso-base. Valores repetidos em posições diferentes ainda podem gerar listas repetidas. Esta implementação armazena todos os resultados e faz muitas chamadas recursivas, por isso é mais adequada para aprendizado ou entradas pequenas; quando não precisar personalizar a construção, prefira o iterador da biblioteca padrão.

Abordagem iterativa para gerar permutações

Também é possível construir os resultados inserindo cada novo item em todas as posições das ordenações parciais já coletadas. A lista começa com uma ordenação vazia e, a cada etapa, cresce por um fator igual ao comprimento da entrada até então. Essa abordagem evita chamadas recursivas, mas ainda armazena todos os 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]]

A ordem de inserção determina a ordem em que este método retorna os resultados; ela não altera quais permutações são geradas. Escolha essa abordagem quando a construção passo a passo atender à sua tarefa e considere a memória necessária para manter o resultado completo.

Conclusão

Use itertools.permutations para obter um iterador conciso que produz resultados sob demanda, definindo r quando precisar de um comprimento específico. Use recursão ou inserção iterativa para personalizar ou estudar a construção. Uma lista com comprimento n tem n! permutações completas quando suas posições são distintas, portanto o tempo de processamento e o espaço para armazenar um resultado materializado crescem rapidamente. Para entradas maiores, processe o iterador conforme necessário ou gere apenas os comprimentos e as seleções relevantes ao problema.

Perguntas frequentes

1. O que é uma permutação?
   É uma seleção ordenada de itens. Por exemplo, [1, 2] e [2, 1] são permutações diferentes porque a ordem muda.

2. Como itertools.permutations funciona?
   A função produz tuplas de comprimento r a partir do iterável de entrada. Se r não for informado, ela usa o comprimento total da entrada. Os resultados são produzidos sob demanda, mas converter o iterador em uma lista armazena todos eles.

3. O que acontece quando a entrada contém valores duplicados?
   A função considera posições, não se os valores são iguais. Por isso, valores repetidos na entrada podem gerar tuplas idênticas. Converter todos os resultados em um conjunto pode remover tuplas repetidas após a geração, desde que seus elementos possam ser usados em conjuntos, mas isso não evita que sejam geradas. Para evitar trabalho duplicado, use um algoritmo que ignore escolhas iguais em cada etapa.

4. Quantas permutações existem?
   Para n posições distintas, há n! permutações completas. Se forem escolhidas apenas r posições, a quantidade é n! / (n - r)!.

5. Qual é o tamanho máximo de entrada que posso usar?
   Não há um limite único que sirva para toda máquina ou tarefa. A quantidade fatorial pode tornar até uma entrada moderada custosa de processar, e armazenar todos os resultados exige bastante memória. Prefira processar os resultados sob demanda ou usar um valor menor de r quando não precisar de todos os resultados completos ao mesmo tempo.