Python gir direkte metoder for å finne permutasjoner og kombinasjoner av en sekvens. Disse metodene finnes i itertools-pakken.
Permutasjon
Importer først itertools-pakken for å implementere permutasjonsmetoden i python. Denne metoden tar en liste som input og returnerer en objektliste med tupler som inneholder alle permutasjoner i en listeform.
Python3
bæsj
# 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)> |
>
>
Produksjon:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Tidskompleksitet: O(n!), hvor n er lengden på inndatalisten. Dette er fordi det er n! permutasjoner av n elementer, og programmet genererer og skriver ut alle.
Ekstra plass: O(n!), siden programmet trenger å lagre alle n! permutasjoner i minnet før du skriver dem ut. Nærmere bestemt, perm-variabelen opprettet ved å kalle permutasjoner([1, 2, 3]) lagrer alle n! permutasjoner i minnet som en liste.
Det genererer n! permutasjoner hvis lengden på inngangssekvensen er n.
Hvis du ønsker å få permutasjoner av lengde L, implementer det på denne måten.
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)> |
>
>
Produksjon:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
Tidskompleksiteten til dette programmet er O(n^r) der n er lengden på inngangsmatrisen og r er lengden på permutasjonene som skal genereres.
Romkompleksiteten er også O(n^r) ettersom alle permutasjoner lagres i minnet før utskrift.
Det genererer nCr * r! permutasjoner hvis lengden på inngangssekvensen er n og inngangsparameteren er r.
Kombinasjon
Denne metoden tar en liste og en input r som input og returnerer en objektliste med tupler som inneholder alle mulige kombinasjoner av lengde r i en listeform.
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)> |
>
>
Produksjon:
(1, 2) (1, 3) (2, 3)>
1. Kombinasjoner sendes ut i leksikografisk sorteringsrekkefølge. Så hvis inndatalisten er sortert, vil kombinasjonstuplene bli produsert i sortert rekkefølge.
Python3
mvc for 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)> |
>
>
Produksjon:
(1, 2) (1, 3) (2, 3)>
2. Elementer behandles som unike basert på deres posisjon, ikke på deres verdi. Så hvis inngangselementene er unike, vil det ikke være gjentatte verdier i hver kombinasjon.
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)> |
kamelvesken python
>
>
Produksjon:
(2, 1) (2, 3) (1, 3)>
3. Hvis vi vil lage en kombinasjon av det samme elementet til det samme elementet, bruker vi kombinasjoner_med_erstatning.
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)> |
>
>
Produksjon:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>