16.5. Enumerazione combinatoria#

In Python è abbastanza facile generare tutti i tipi di raggruppamenti visti finora. In particolare, il modulo itertools, fornisce iteratori efficienti che permettono di generare in sequenza tutti i possibili raggruppamenti di un dato tipo, senza mai mantenerli tutti insieme in memoria.

Iteratori e memoria

Le funzioni di itertools restituiscono iteratori, non liste. Gli elementi vengono generati uno alla volta solo quando richiesti, senza mai caricare l'intera sequenza in memoria. Questo è particolarmente vantaggioso quando \(n\) e \(k\) sono grandi: per esempio, scegliere tutte le squadre da 5 eroi tra i 50 personaggi del Marvel Cinematic Universe produrrebbe \(c_{50,5} = \) 2 118 760 combinazioni. Nell'ipotesi che la descrizione di una squadra richieda di specificare un identificatore intero per ogni membro, materializzare tutte le squadre possibili in una lista richiederebbe verosimilmente alcune decine di megabyte di RAM, mentre l'approccio basato su iteratore manterrebbe di volta in volta in memoria un'unica squadra — e per questo basterebbero una ventina di byte!

Se tuttavia un'applicazione richiedesse di salvare in memoria tutte le descrizioni, per esempio perché si deve svolgere un'elaborazione delle squadre che non può essere fatta in modo sequenziale, gli iteratori possono essere convertiti esplicitamente in list usando list.

16.5.1. Permutazioni semplici#

Gli oggetti della classe itertools.permutations sono degli iteratori che, quando vengono attraversati, generano tutte le permutazioni semplici degli elementi contenuti nell'oggetto usato per istanziare la classe stessa. Per esempio, eseguendo la cella seguente si ottiene un elenco delle possibili permutazioni dei Fantastici 4, analogo a quello della 12:

import itertools as it

fantastic_4 = ['f', 'i', 't', 'c']
for i, p in enumerate(it.permutations(fantastic_4)):
    print(p, end='\n' if (i+1) % 3 == 0 else '  ')

('f', 'i', 't', 'c')  ('f', 'i', 'c', 't')  ('f', 't', 'i', 'c')
('f', 't', 'c', 'i')  ('f', 'c', 'i', 't')  ('f', 'c', 't', 'i')
('i', 'f', 't', 'c')  ('i', 'f', 'c', 't')  ('i', 't', 'f', 'c')
('i', 't', 'c', 'f')  ('i', 'c', 'f', 't')  ('i', 'c', 't', 'f')
('t', 'f', 'i', 'c')  ('t', 'f', 'c', 'i')  ('t', 'i', 'f', 'c')
('t', 'i', 'c', 'f')  ('t', 'c', 'f', 'i')  ('t', 'c', 'i', 'f')
('c', 'f', 'i', 't')  ('c', 'f', 't', 'i')  ('c', 'i', 'f', 't')
('c', 'i', 't', 'f')  ('c', 't', 'f', 'i')  ('c', 't', 'i', 'f')

In altre parole, il codice precedente genera tutte le \(p_4 = 24\) permutazioni dei quattro membri della squadra.

16.5.2. Permutazioni con ripetizione#

Il modulo itertools non offre la possibilità di generare direttamente tutte le permutazioni con ripetizione di un insieme di oggetti distinguibili a gruppi. È però abbastanza facile ottenere queste permutazioni partendo da quelle semplici e filtrando i doppioni[1], per esempio inserendo le permutazioni in un insieme, così da potere ignorare le loro successive occorrenze. La cella seguente utilizza un approccio di questo tipo per produrre un elenco simile a quello della 13:

clones = ['k', 'k', 'p', 'p', 'p']
seen = set()
for t in it.permutations(clones):
    if t not in seen:
        print(t, end='\n' if (len(seen)+1) % 3 == 0 else '  ')
        seen.add(t)

('k', 'k', 'p', 'p', 'p')  ('k', 'p', 'k', 'p', 'p')  ('k', 'p', 'p', 'k', 'p')
('k', 'p', 'p', 'p', 'k')  ('p', 'k', 'k', 'p', 'p')  ('p', 'k', 'p', 'k', 'p')
('p', 'k', 'p', 'p', 'k')  ('p', 'p', 'k', 'k', 'p')  ('p', 'p', 'k', 'p', 'k')
('p', 'p', 'p', 'k', 'k')

16.5.3. Disposizioni con ripetizione#

È facile rendersi conto che le disposizioni con ripetizione degli oggetti di un insieme \(A\) in \(k \in \mathbb N\) sono esattamente gli elementi del prodotto cartesiano

\[A^k = \underbrace{A \times A \times \cdots \times A}_{\text{$k$ volte}} \enspace,\]

e che quindi si possono ottenere direttamente generando gli elementi del prodotto cartesiano iterato, cosa che si ottiene facilmente usando l'iteratore restituito da itertools.product, che quando viene invocato usando il parametro opzionale repeat permette appunto di calcolare il prodotto di un insieme con se stesso per un dato numero di volte. La cella seguente mostra come riprodurre in tal modo le disposizioni con ripetizione della 14.

alpha_flight = ['g', 's', 'n', 'a']
for i, d in enumerate(it.product(alpha_flight, repeat=3)):
    print(d, end='\n' if (i+1) % 4 == 0 else '  ')
    if i == 15:
        break

('g', 'g', 'g')  ('g', 'g', 's')  ('g', 'g', 'n')  ('g', 'g', 'a')
('g', 's', 'g')  ('g', 's', 's')  ('g', 's', 'n')  ('g', 's', 'a')
('g', 'n', 'g')  ('g', 'n', 's')  ('g', 'n', 'n')  ('g', 'n', 'a')
('g', 'a', 'g')  ('g', 'a', 's')  ('g', 'a', 'n')  ('g', 'a', 'a')

Questo codice non stampa tutte le \(D_{4, 3} = 64\) disposizioni con ripetizione, perché viene forzata l'uscita dal ciclo for dopo averne considerato \(16\), per evitare un output inutilmente lungo.

16.5.4. Disposizioni senza ripetizione#

In virtù della relazione che sussiste tra le permutazioni semplici e le disposizioni senza ripetizione, queste ultime possono essere generate utilizzando itertools.permutations, specificando un secondo argomento che indica il numero di posti. Ad esempio, nella cella seguente vengono prodotte tutte le \(d_{4, 3} = 24\) disposizioni semplici evidenziate in grassetto nella 14.

for i, d in enumerate(it.permutations(alpha_flight, 3)):
    print(d, end='\n' if (i+1) % 4 == 0 else '  ')

('g', 's', 'n')  ('g', 's', 'a')  ('g', 'n', 's')  ('g', 'n', 'a')
('g', 'a', 's')  ('g', 'a', 'n')  ('s', 'g', 'n')  ('s', 'g', 'a')
('s', 'n', 'g')  ('s', 'n', 'a')  ('s', 'a', 'g')  ('s', 'a', 'n')
('n', 'g', 's')  ('n', 'g', 'a')  ('n', 's', 'g')  ('n', 's', 'a')
('n', 'a', 'g')  ('n', 'a', 's')  ('a', 'g', 's')  ('a', 'g', 'n')
('a', 's', 'g')  ('a', 's', 'n')  ('a', 'n', 'g')  ('a', 'n', 's')

16.5.5. Combinazioni#

Il modulo itertools contiene due classi combinations e combinations_with_replacement i cui oggetti sono iteratori sulle combinazioni, rispettivamente semplici e con ripetizione. Per esempio, la cella seguente stampa le combinazioni semplici di tre poteri di Peter Petrelli (vedi Esempio 15), nel caso questi possano essere selezionati da un gruppo di cinque superpoteri.

powers = ['telepatia','invisibilità', 'psicocinesi',
          'rigenerazione', 'precognizione']
for c in it.combinations(powers, 3):
    print(c)

('telepatia', 'invisibilità', 'psicocinesi')
('telepatia', 'invisibilità', 'rigenerazione')
('telepatia', 'invisibilità', 'precognizione')
('telepatia', 'psicocinesi', 'rigenerazione')
('telepatia', 'psicocinesi', 'precognizione')
('telepatia', 'rigenerazione', 'precognizione')
('invisibilità', 'psicocinesi', 'rigenerazione')
('invisibilità', 'psicocinesi', 'precognizione')
('invisibilità', 'rigenerazione', 'precognizione')
('psicocinesi', 'rigenerazione', 'precognizione')

Analogamente, il codice qui sotto genera tutte le combinazioni con ripetizione considerate nella 15.

for c in it.combinations_with_replacement(['k','p'], 4):
    print(c)

('k', 'k', 'k', 'k')
('k', 'k', 'k', 'p')
('k', 'k', 'p', 'p')
('k', 'p', 'p', 'p')
('p', 'p', 'p', 'p')

Vero o falso?#

Analizzate ciascuna delle seguenti affermazioni, che riguardano le combinazioni, e dite se è vera o falsa, motivando il vostro ragionamento. Cliccate su di essa per visualizzare la risposta corretta.

itertools.permutations(A) genera tutte le permutazioni semplici degli elementi di A.

Vera. itertools.permutations(A) produce tutte le sequenze ordinate degli elementi di A senza ripetizioni, che corrispondono esattamente alle permutazioni semplici. Per un insieme di \(n\) oggetti, il numero di sequenze generate è \(p_n = n!\), come verificato nell' Esercizio 71.

itertools.product(A, repeat=k) genera le disposizioni con ripetizione di \(k\) elementi scelti da A.

Vera. itertools.product(A, repeat=k) restituisce il prodotto cartesiano \(A^k\), ovvero tutte le sequenze ordinate di lunghezza \(k\) con possibilità di ripetere gli elementi. Questo corrisponde esattamente alle disposizioni con ripetizione \(D_{n,k} = n^k\), come mostrato nell' Esercizio 73.

itertools.combinations(A, k) restituisce sequenze ordinate di \(k\) elementi di A.

Falsa. itertools.combinations(A, k) genera sottoinsiemi non ordinati di \(k\) elementi: due sequenze con gli stessi elementi in ordine diverso corrispondono alla stessa combinazione e vengono restituite una sola volta. Per generare sequenze ordinate bisogna usare itertools.permutations(A, k), che produce le disposizioni semplici.

I generatori di itertools mantengono in memoria tutti gli elementi generati per poterli restituire su richiesta.

Falsa. I generatori di itertools producono un elemento alla volta senza memorizzare quelli precedenti, occupando quindi memoria costante indipendentemente dal numero totale di elementi. Questo li rende efficienti anche quando il numero combinatorio è molto grande, come discusso nell' Esercizio 75.

itertools.permutations(A, k) con \(k < |A|\) genera le disposizioni semplici di \(k\) elementi scelti da A.

Vera. Quando si passa un secondo argomento \(k\), itertools.permutations(A, k) produce tutte le sequenze ordinate di \(k\) elementi distinti scelti da A, senza ripetizioni. Il numero di tali sequenze è \(d_{n,k} = n!/(n-k)!\), che corrisponde esattamente alla formula delle disposizioni semplici.

itertools fornisce una funzione dedicata per generare direttamente le permutazioni con ripetizione di un multiinsieme.

Falsa. itertools non offre una funzione specifica per le permutazioni con ripetizione. Per ottenerle bisogna generare tutte le permutazioni con itertools.permutations e filtrare i duplicati tramite un insieme, come mostrato nell'Esercizio 78.

16.5.6. Esercizi#

Esercizio 70 (•)

Generate e stampate tutti modi in cui è possibile assegnare tre turni di pattuglia ai cinque Teen Titans (Robin, Starfire, Raven, Beast Boy, Cyborg), eventualmente assegnando a uno stesso supereroe anche più di un turno. Contate e stampate inoltre il numero totale di turnazioni possibili.

Esercizio 71 (•)

Se nell'esercizio precedente l'unica richiesta fosse stata quella di contare il numero di turnazioni differenti, senza stamparle, esisterebbero dei modi più efficienti di rispondere alla domanda?

Esercizio 72 (•)

Generate e stampate tutte le possibili coppie formate dai sei membri dei Watchmen (Rorschach, Nite Owl, Silk Spectre, Ozymandias, Dottor Manhattan, Comedian).

Esercizio 73 (•)

Calcolate quante tra le combinazioni con ripetizione di Dupli-Kate e Multi-Paul in quattro posti contengono almeno un clone di Kate.

Esercizio 74 (•)

Riconsiderate l'esercizio precedente, risolvendolo usando una list comprehension.

Esercizio 75 (•)

Contate quante disposizioni con ripetizione dei \(21\) membri regolari della Legion of Super-Heroes in \(3\) posti soddisfano la condizione che il primo e il terzo posto siano occupati dallo stesso eroe, senza memorizzare l'intera lista.

Esercizio 76 (••)

Quante sono le disposizioni semplici dei quattro membri degli Alpha Flight (vedi l’Esempio 11) in tre posti che non includono Guardian? Verificate sperimentalmente la risposta a questa domanda generando tutte le disposizioni e contando quelle che lo escludono.

Esercizio 77 (••)

Scrivete una funzione compute_combinatorics(n, k) che, usando gli iteratori di itertools, conta il numero di disposizioni con ripetizione, disposizioni semplici e combinazioni semplici di n oggetti in k posti. La funzione deve restituire un dizionario le cui chiavi sono le stringhe 'D', 'd' e 'c', associate rispettivamente alle disposizioni con ripetizione, alle disposizioni semplici e alle combinazioni. Verificate che la funzione si comporti correttamente nel caso in cui gli argomenti n e k sono rispettivamente uguali a \(5\) e \(3\).

Esercizio 78 (••)

Generate tutte le permutazioni degli oggetti nel multiinsieme che contiene due cloni di Dupli-Kate e tre di Multi-Paul, inserendo in un insieme tutte le permutazioni semplici.

Esercizio 79 (••)

Leggete la documentazione della classe itertools.islice, e utilizzatela per generare e stampare solamente dieci permutazioni semplici dei cinque membri dei Doom Patrol (Robotman, Negative Man, Elasti-Girl, Crazy Jane, Flex Mentallo), senza generare né scorrere le restanti \(5! - 10 = 110\) permutazioni.

Esercizio 80 (••)

Stampate tutte le combinazioni di tre superpoteri, scelti tra telepatia, invisibilità, psicocinesi, rigenerazione e precognizione, escludendo quelle che contengono simultaneamente telepatia e psicocinesi. Quante sono queste combinazioni?

Esercizio 81 (•••)

Scrivete un generatore Python che, dato un elenco di eroi e un intero \(k\), produca tutte le coppie di squadre disgiunte di \(k\) eroi ciascuna. Verificate il comportamento del generatore utilizzando i nove Young Avengers (Patriot, Hulkling, Wiccan, Speed, Stature, Vision, Kate Bishop, Noh-Varr e Jonas) e \(k = 2\), tenendo conto che il numero di coppie di squadre — in questo caso — deve essere uguale a \(c_{9,2} \cdot c_{7,2} = 36 \cdot 21 = 756\).

16.5.7. Concetti fondamentali#

Pensate ai concetti fondamentali illustrati in questo paragrafo ed elencateli. Nella lista qui sotto sono già presenti gli stessi concetti, ma nascosti. Cliccate sul pulsante per mostrarli sotto forma di parole chiave, quindi confrontateli con la vostra lista. Provate infine a descrivere ciascun concetto con parole vostre.

Contenuti