Python poskytuje priame metódy na nájdenie permutácií a kombinácií sekvencie. Tieto metódy sú prítomné v balíku itertools.
Permutácia
Najprv importujte balík itertools na implementáciu metódy permutácií v pythone. Táto metóda berie zoznam ako vstup a vracia objektový zoznam ničiek, ktoré obsahujú všetky permutácie vo forme zoznamu.
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)> |
>
>
Výkon:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Časová zložitosť: O(n!), kde n je dĺžka zoznamu vstupov. Je to preto, že existuje n! permutácií n prvkov a program ich všetky vygeneruje a vytlačí.
Pomocný priestor: O(n!), pretože program potrebuje uložiť všetky n! permutácií v pamäti pred ich vytlačením. Konkrétne premenná perm vytvorená volaním permutácií([1, 2, 3]) ukladá všetkých n! permutácií v pamäti ako zoznam.
To generuje n! permutácií, ak dĺžka vstupnej postupnosti je n.
Ak chcete získať permutácie dĺžky L, implementujte to týmto spôsobom.
Python3
java nahradiť všetky
# 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)> |
>
>
Výkon:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
Časová zložitosť tohto programu je O(n^r), kde n je dĺžka vstupného poľa a r je dĺžka permutácií, ktoré sa majú vygenerovať.
Priestorová zložitosť je tiež O(n^r), pretože všetky permutácie sú uložené v pamäti pred tlačou.
Generuje nCr * r! permutácií, ak dĺžka vstupnej postupnosti je n a vstupný parameter je r.
Kombinácia
Táto metóda berie zoznam a vstup r ako vstup a vracia objektový zoznam ničiek, ktoré obsahujú všetky možné kombinácie dĺžky r vo forme zoznamu.
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)> |
>
>
Výkon:
(1, 2) (1, 3) (2, 3)>
1. Kombinácie sú vydávané v lexikografickom poradí zoradenia vstupu. Takže ak je zoznam vstupov zoradený, kombinované n-tice sa vytvoria v zoradenom poradí.
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)> |
>
>
Výkon:
(1, 2) (1, 3) (2, 3)>
2. Prvky sa považujú za jedinečné na základe ich polohy, nie hodnoty. Ak sú teda vstupné prvky jedinečné, v každej kombinácii nebudú žiadne opakované hodnoty.
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)> |
>
>
Výkon:
(2, 1) (2, 3) (1, 3)>
3. Ak chceme vytvoriť kombináciu rovnakého prvku s rovnakým prvkom, použijeme kombináciu_s_nahradením.
Python3
applet applet
# 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)> |
>
>
Výkon:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>