In un precedente articolo (qui) illustravo un semplice algoritmo per la ricerca delle combinazioni, sviluppato originariamente in linguaggio C e poi successivamente tradotto in Python.
In realtà in Python è tutto molto più semplice...
In Python esiste il modulo itertools che fornisce una serie di funzioni per creare degli iterators (https://docs.python.org/dev/library/itertools.html): tra queste funzioni troviamo una serie di utili metodi di combinatoria.
Per una rapida introduzione suggerisco la lettura di questo articolo http://thomas-cokelaer.info/blog/2012/11/how-do-use-itertools-in-python-to-build-permutation-or-combination/
Ritornando a quanto avevo scritto nell'articolo precedente, ecco la routine per generare le combinazioni di n elementi su k posizioni (n risulta dalla lunghezza della stringa passata in input):
def combinaric( lst, set, curr, n, k ):
#print( "combinaric: n=" + str(n) + " k=" + str(k) + " curr=" + curr)
for i in range(0,len(set)):
loccurr = curr + set[i]
if k==1:
lst.append(loccurr)
else:
combinaric( lst, set[i+1:], loccurr, n-1, k-1)
def combina( set, k ):
lst = [];
n = len(set)
combinaric( lst, set, "", n, k )
return lst
if __name__ == "__main__":
lst = combina( "ABCDE", 3 )
for i in range(0,len(lst)):
print("->"+lst[i])
Il risultato a video è il seguente:
->ABC
->ABD
->ABE
->ACD
->ACE
->ADE
->BCD
->BCE
->BDE
->CDE
Ecco invece la versione con itertools:
import itertools
if __name__ == "__main__":
lst = list(itertools.combinations(["A","B","C","D","E"], 3))
for i in range(0,len(lst)):
print("->"+str(lst[i]))
Bisogna fare attenzione ad inserire la import iniziale, per caricare il modulo itertools; c'è anche da notare che viene generato un elenco di tuple e quindi per stampare a video ho dovuto utilizzare str().
Il risultato a video è il seguente:
->('A', 'B', 'C')
->('A', 'B', 'D')
->('A', 'B', 'E')
->('A', 'C', 'D')
->('A', 'C', 'E')
->('A', 'D', 'E')
->('B', 'C', 'D')
->('B', 'C', 'E')
->('B', 'D', 'E')
->('C', 'D', 'E')
Leggendo la documentazione della funzione (https://docs.python.org/dev/library/itertools.html#itertools.combinations) si nota come il primo argomento è un qualsiasi oggetto iterable e allora ecco la versione a cui passiamo direttamente la stringa:
import itertools
if __name__ == "__main__":
lst = list(itertools.combinations("ABCDE", 3))
for i in range(0,len(lst)):
print("->"+str(lst[i]))
Sempre con itertools è possibile generare le permutazioni semplici:
lst = list(itertools.permutations("ABCDE"))
Il risultato è una lista di 120 tuple:
->('A', 'B', 'C', 'D', 'E')
->('A', 'B', 'C', 'E', 'D')
->('A', 'B', 'D', 'C', 'E')
->('A', 'B', 'D', 'E', 'C')
...
->('E', 'D', 'B', 'A', 'C')
->('E', 'D', 'B', 'C', 'A')
->('E', 'D', 'C', 'A', 'B')
->('E', 'D', 'C', 'B', 'A')
Si possono generare disposizioni, semplicemente impostando opportunamente il secondo parametro della funzione permutations():
lst = list(itertools.permutations("ABCDE", 3))
Il risultato in questo caso è una lista di 60 tuple:
->('A', 'B', 'C')
->('A', 'B', 'D')
->('A', 'B', 'E')
->('A', 'C', 'B')
...
->('E', 'C', 'D')
->('E', 'D', 'A')
->('E', 'D', 'B')
->('E', 'D', 'C')
E' anche possibile ottenere il prodotto cartesiano di due oggetti iterable:
lst = list(itertools.product("ABCDE","123"))
Ecco il risultato, una lista 15 tuple:
->('A', '1')
->('A', '2')
->('A', '3')
->('B', '1')
->('B', '2')
->('B', '3')
->('C', '1')
->('C', '2')
->('C', '3')
->('D', '1')
->('D', '2')
->('D', '3')
->('E', '1')
->('E', '2')
->('E', '3')
Come si può vedere il modulo itertools ci fornisce dei metodi molto potenti; consiglio di visitare la documentazione di Python per avere la lista completa delle funzionalità.
Un'ultima nota: ho conosciuto il modulo itertools leggendo "Learning Python" di Fabrizio Romano (link), un testo estremamente utile perchè introduce il linguaggio fornendo fin dall'inizio degli esempi pratici, facendo capire come si utilizza il linguaggio in maniera professionale.
