Python proporciona mètodes directes per trobar permutacions i combinacions d'una seqüència. Aquests mètodes estan presents al paquet itertools.
Permutació
Primer importeu el paquet itertools per implementar el mètode de permutacions a Python. Aquest mètode pren una llista com a entrada i retorna una llista d'objectes de tuples que contenen totes les permutacions en forma de llista.
Python 3
# 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)> |
>
>
Sortida:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Complexitat temporal: O(n!), on n és la longitud de la llista d'entrada. Això és perquè hi ha n! permutacions de n elements, i el programa els genera i imprimeix tots.
Espai auxiliar: O(n!), ja que el programa necessita emmagatzemar tots els n! permutacions a la memòria abans d'imprimir-les. Concretament, la variable perm creada cridant a permutations([1, 2, 3]) emmagatzema tots els n! permutacions a la memòria com una llista.
Genera n! permutacions si la longitud de la seqüència d'entrada és n.
Si voleu obtenir permutacions de longitud L, implementeu-ho d'aquesta manera.
Python 3
# 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)> |
>
>
Sortida:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
La complexitat temporal d'aquest programa és O(n^r) on n és la longitud de la matriu d'entrada i r és la durada de les permutacions que s'han de generar.
La complexitat de l'espai també és O(n^r) ja que totes les permutacions s'emmagatzemen a la memòria abans d'imprimir-les.
Genera nCr * r! permutacions si la longitud de la seqüència d'entrada és n i el paràmetre d'entrada és r.
Combinació
Aquest mètode pren una llista i una entrada r com a entrada i retorna una llista d'objectes de tuples que contenen totes les combinacions possibles de longitud r en forma de llista.
Python 3
# 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)> |
>
>
Sortida:
(1, 2) (1, 3) (2, 3)>
1. Les combinacions s'emeten per ordre d'entrada lexicogràfic. Per tant, si la llista d'entrada està ordenada, les tuples de combinació es produiran en ordre ordenat.
Python 3
# 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)> |
>
>
Sortida:
(1, 2) (1, 3) (2, 3)>
2. Els elements es tracten com a únics en funció de la seva posició, no pel seu valor. Així, si els elements d'entrada són únics, no hi haurà valors repetits en cada combinació.
Python 3
# 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)> |
llocs web de pel·lícules similars a 123movies
>
>
Sortida:
(2, 1) (2, 3) (1, 3)>
3. Si volem fer una combinació del mateix element amb el mateix element, fem servir combinacions_amb_reemplaçament.
Python 3
# 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)> |
>
>
Sortida:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>