Python nodrošina tiešas metodes, lai atrastu secības permutācijas un kombinācijas. Šīs metodes ir iekļautas itertools pakotnē.
Permutācija
Vispirms importējiet itertools pakotni, lai ieviestu permutāciju metodi programmā python. Šī metode izmanto sarakstu kā ievadi un atgriež objektu sarakstu ar kortežiem, kas saraksta formā satur visas permutācijas.
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)> |
>
>
Izvade:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Laika sarežģītība: O(n!), kur n ir ievades saraksta garums. Tas ir tāpēc, ka ir n! n elementu permutācijas, un programma tos visus ģenerē un izdrukā.
Palīgtelpa: O(n!), jo programmai jāsaglabā visi n! permutācijas atmiņā pirms to drukāšanas. Konkrēti, perm mainīgais, kas izveidots, izsaucot permutācijas ([1, 2, 3]), saglabā visus n! permutācijas atmiņā kā sarakstu.
Tas rada n! permutācijas, ja ievades secības garums ir n.
Ja vēlaties iegūt L garuma permutācijas, ieviesiet to šādā veidā.
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)> |
>
>
Izvade:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
Šīs programmas laika sarežģītība ir O(n^r), kur n ir ievades masīva garums un r ir ģenerējamo permutāciju garums.
Telpas sarežģītība ir arī O(n^r), jo visas permutācijas pirms drukāšanas tiek saglabātas atmiņā.
Tas ģenerē nCr * r! permutācijas, ja ievades secības garums ir n un ievades parametrs ir r.
Kombinācija
Šī metode izmanto sarakstu un ievadi r kā ievadi un atgriež objektu sarakstu ar korežiem, kas saraksta formā satur visas iespējamās garuma r kombinācijas.
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)> |
>
>
Izvade:
(1, 2) (1, 3) (2, 3)>
1. Kombinācijas tiek izvadītas ievades leksikogrāfiskā kārtošanas secībā. Tātad, ja ievades saraksts ir sakārtots, kombināciju korteži tiks izveidoti sakārtotā secībā.
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)> |
>
>
Izvade:
(1, 2) (1, 3) (2, 3)>
2. Elementi tiek uzskatīti par unikāliem, pamatojoties uz to stāvokli, nevis vērtību. Tātad, ja ievades elementi ir unikāli, katrā kombinācijā netiks atkārtotas vērtības.
Python3
cast string kā int
# 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)> |
>
>
Izvade:
(2, 1) (2, 3) (1, 3)>
3. Ja mēs vēlamies izveidot viena un tā paša elementa kombināciju vienam un tam pašam elementam, mēs izmantojam kombinācijas_ar_replacement.
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)> |
>
>
Izvade:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>