Python ponuja neposredne metode za iskanje permutacij in kombinacij zaporedja. Te metode so prisotne v paketu itertools.
Permutacija
Najprej uvozite paket itertools za implementacijo metode permutacij v python. Ta metoda vzame seznam kot vhod in vrne seznam objektov tulp, ki vsebujejo vse permutacije v obliki seznama.
Python3
# 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)> |
>
>
Izhod:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Časovna zahtevnost: O(n!), kjer je n dolžina vhodnega seznama. To je zato, ker obstaja n! permutacij n elementov, program pa vse generira in natisne.
Pomožni prostor: O(n!), saj mora program shraniti vse n! permutacije v pomnilniku, preden jih natisnete. Natančneje, spremenljivka perm, ustvarjena s klicem permutations([1, 2, 3]), shrani vse n! permutacije v pomnilniku kot seznam.
Ustvarja n! permutacije, če je dolžina vhodnega zaporedja n.
Če želite dobiti permutacije dolžine L, jih implementirajte na ta način.
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)> |
>
>
Izhod:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
Časovna kompleksnost tega programa je O(n^r), kjer je n dolžina vhodne matrike in r dolžina permutacij, ki jih je treba generirati.
Kompleksnost prostora je tudi O(n^r), saj so vse permutacije pred tiskanjem shranjene v pomnilniku.
Ustvari nCr * r! permutacije, če je dolžina vhodnega zaporedja n in je vhodni parameter r.
Kombinacija
Ta metoda vzame seznam in vnos r kot vhod ter vrne objektni seznam tulp, ki vsebujejo vse možne kombinacije dolžine r v obliki seznama.
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)> |
>
>
Izhod:
(1, 2) (1, 3) (2, 3)>
1. Kombinacije so oddane v leksikografskem vrstnem redu vnosa. Torej, če je vhodni seznam razvrščen, bodo kombinirane tuple izdelane v razvrščenem vrstnem redu.
Python3
# 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)> |
>
vrednost niza java
>
Izhod:
(1, 2) (1, 3) (2, 3)>
2. Elementi se obravnavajo kot edinstveni glede na njihov položaj, ne glede na njihovo vrednost. Torej, če so vhodni elementi edinstveni, v vsaki kombinaciji ne bo ponavljajočih se vrednosti.
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)> |
>
>
Izhod:
(2, 1) (2, 3) (1, 3)>
3. Če želimo narediti kombinacijo istega elementa z istim elementom, potem uporabimo kombinacije_z_zamenjavo.
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)> |
>
>
Izhod:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>