Come generare tutte le permutazioni di una lista in Python

Per generare le permutazioni di una lista in Python, puoi usare la libreria standard oppure scegliere un algoritmo ricorsivo o iterativo se vuoi personalizzare il procedimento. Una permutazione è un ordinamento di alcuni elementi: a differenza di una combinazione, l’ordine è rilevante. Il numero di risultati cresce in modo fattoriale, quindi generare tutti gli ordinamenti è pratico solo con input di dimensioni contenute.

Usare la libreria itertools

Nella maggior parte dei casi, usa itertools.permutations. La funzione restituisce un iteratore di tuple, così puoi elaborare i risultati uno alla volta senza creare subito una lista. Per impostazione predefinita, r è pari alla lunghezza dell’input e ogni risultato contiene tutti gli elementi. Nell’esempio, r=2 seleziona coppie ordinate e il ciclo genera risultati di ogni lunghezza da uno a tre.

Con la lista [1, 2, 3], il programma stampa:

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

L’argomento r imposta il numero di elementi in ogni tupla. Per generare tutte le lunghezze non vuote, richiama la funzione per ogni valore di r da 1 alla lunghezza dell’input, come nell’esempio. itertools.permutations considera le posizioni degli elementi: se un valore compare più volte nell’input, alcune tuple risultanti possono essere identiche.

Consulta la documentazione ufficiale di itertools per la firma completa e il comportamento della funzione.

Funzione ricorsiva per le permutazioni

Una soluzione ricorsiva sceglie un elemento alla volta e lo antepone a ogni permutazione degli elementi rimanenti. Il caso base restituisce una lista contenente un solo ordinamento vuoto: in questo modo la costruzione funziona con input di qualsiasi lunghezza, anche zero. Questa versione restituisce liste anziché tuple ed è utile per studiare o personalizzare il procedimento.

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

A ogni chiamata ricorsiva viene rimossa una posizione, quindi l’input rimanente si riduce fino a raggiungere il caso base. Valori ripetuti in posizioni diverse possono comunque produrre liste duplicate. Questa implementazione conserva tutti i risultati e crea molte chiamate ricorsive: è adatta soprattutto per imparare o per input piccoli. Se non ti serve personalizzare la costruzione, usa l’iteratore della libreria standard.

Approccio iterativo per generare permutazioni

Puoi anche costruire i risultati inserendo ogni nuovo elemento in tutte le posizioni possibili degli ordinamenti parziali già raccolti. La lista inizia con un solo ordinamento vuoto e, a ogni passaggio, cresce di un fattore pari alla lunghezza dell’input raggiunta. Questo metodo evita le chiamate ricorsive, ma continua a conservare tutti i risultati.

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

L’ordine di inserimento determina l’ordine in cui questo metodo restituisce i risultati, ma non cambia quali permutazioni vengono generate. Sceglilo se la costruzione passo per passo è adatta al tuo caso e considera la memoria necessaria per conservare l’intero risultato.

Conclusione

Usa itertools.permutations per ottenere un iteratore conciso e lazy, impostando r quando ti serve una lunghezza specifica. Scegli la ricorsione o l’inserimento iterativo se vuoi personalizzare o comprendere la costruzione. Una lista di lunghezza n ha n! permutazioni complete quando le posizioni sono distinte; perciò il tempo di elaborazione e lo spazio necessario per materializzare i risultati crescono rapidamente. Con input più grandi, elabora l’iteratore man mano oppure genera soltanto le lunghezze e le selezioni che ti servono.

Domande frequenti

1. Che cos’è una permutazione?
   È una selezione ordinata di elementi. Per esempio, [1, 2] e [2, 1] sono permutazioni diverse perché cambia l’ordine.

2. Come funziona itertools.permutations?
   Restituisce tuple di lunghezza r ricavate dall’iterabile di input. Se ometti r, usa l’intera lunghezza dell’input. I risultati vengono prodotti in modo lazy, ma convertire l’iteratore in una lista li conserva tutti in memoria.

3. Cosa succede se l’input contiene valori duplicati?
   La funzione considera le posizioni, non l’uguaglianza dei valori. Valori ripetuti nell’input possono quindi generare tuple identiche. Se gli elementi sono hashable, convertire tutti i risultati in un insieme può rimuovere le tuple ripetute dopo averle generate, ma non evita di generarle. Per evitare il lavoro duplicato, usa un algoritmo che salta le scelte uguali a ogni passaggio.

4. Quante permutazioni ci sono?
   Per n posizioni distinte ci sono n! permutazioni complete. Se selezioni soltanto r posizioni, il numero è n! / (n - r)!.

5. Quanto può essere grande l’input?
   Non esiste un limite unico adatto a ogni macchina e a ogni problema. La crescita fattoriale può rendere costosa l’elaborazione anche con input moderati, e conservare tutti i risultati richiede molta memoria. Se non ti servono tutti i risultati completi insieme, preferisci l’iterazione lazy o un valore di r più piccolo.