Python fornisce metodi diretti per trovare permutazioni e combinazioni di una sequenza. Questi metodi sono presenti nel pacchetto itertools.
Permutazione
Innanzitutto importa il pacchetto itertools per implementare il metodo delle permutazioni in Python. Questo metodo accetta una lista come input e restituisce un elenco di oggetti di tuple che contengono tutte le permutazioni sotto forma di lista.
Python3
myflixr
# A Python program to print all> # permutations using library function> from> itertools>import> permutations> # Get all permutations of [1, 2, 3]> perm>=> permutations([>1>,>2>,>3>])> # Print the obtained permutations> for> i>in> list>(perm):> >print> (i)> |
>
>
Produzione:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Complessità temporale: O(n!), dove n è la lunghezza dell'elenco di input. Questo perché ci sono n! permutazioni di n elementi e il programma li genera e stampa tutti.
Spazio ausiliario: O(n!), poiché il programma deve memorizzare tutti gli n! permutazioni in memoria prima di stamparle. Nello specifico, la variabile perm creata chiamando permutations([1, 2, 3]) memorizza tutti gli n! permutazioni in memoria come elenco.
Genera n! permutazioni se la lunghezza della sequenza di input è n.
Se vuoi ottenere permutazioni di lunghezza L, implementalo in questo modo.
Python3
# A Python program to print all> # permutations of given length> from> itertools>import> permutations> # Get all permutations of length 2> # and length 2> perm>=> permutations([>1>,>2>,>3>],>2>)> # Print the obtained permutations> for> i>in> list>(perm):> >print> (i)> |
>
>
Produzione:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
La complessità temporale di questo programma è O(n^r) dove n è la lunghezza dell'array di input e r è la lunghezza delle permutazioni da generare.
Anche la complessità dello spazio è O(n^r) poiché tutte le permutazioni vengono archiviate in memoria prima della stampa.
Genera nCr*r! permutazioni se la lunghezza della sequenza di input è n e il parametro di input è r.
Combinazione
Questo metodo accetta una lista e un input r come input e restituisce un elenco di oggetti di tuple che contengono tutte le possibili combinazioni di lunghezza r in una forma di lista.
Python3
# A Python program to print all> # combinations of given length> from> itertools>import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb>=> combinations([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
Produzione:
(1, 2) (1, 3) (2, 3)>
1. Le combinazioni vengono emesse secondo l'ordinamento lessicografico dell'input. Pertanto, se l'elenco di input è ordinato, le tuple di combinazione verranno prodotte in ordine ordinato.
Python3
stringa.sottostringa java
# A Python program to print all> # combinations of a given length> from> itertools>import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb>=> combinations([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
Produzione:
(1, 2) (1, 3) (2, 3)>
2. Gli elementi vengono trattati come unici in base alla loro posizione, non al loro valore. Pertanto, se gli elementi di input sono unici, non ci saranno valori ripetuti in ciascuna combinazione.
Python3
# A Python program to print all combinations> # of given length with unsorted input.> from> itertools>import> combinations> # Get all combinations of [2, 1, 3]> # and length 2> comb>=> combinations([>2>,>1>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
dimensioni dei caratteri in lattice
>
>
Produzione:
(2, 1) (2, 3) (1, 3)>
3. Se vogliamo creare una combinazione dello stesso elemento con lo stesso elemento, allora utilizziamo combinazioni_con_sostituzione.
Python3
# A Python program to print all combinations> # with an element-to-itself combination is> # also included> from> itertools>import> combinations_with_replacement> # Get all combinations of [1, 2, 3] and length 2> comb>=> combinations_with_replacement([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
Produzione:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>