Python oferă metode directe pentru a găsi permutări și combinații ale unei secvențe. Aceste metode sunt prezente în pachetul itertools.
Permutare
Mai întâi importați pachetul itertools pentru a implementa metoda permutărilor în python. Această metodă ia o listă ca intrare și returnează o listă de obiecte de tupluri care conțin toate permutările într-o formă de listă.
Python3
căutarea bfs
# 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)> |
>
>
Ieșire:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Complexitatea timpului: O(n!), unde n este lungimea listei de intrare. Acest lucru se datorează faptului că există n! permutări a n elemente, iar programul le generează și le imprimă pe toate.
Spatiu auxiliar: O(n!), deoarece programul trebuie să stocheze toate n! permutările din memorie înainte de a le imprima. Mai exact, variabila perm creată prin apelarea permutărilor([1, 2, 3]) stochează toate n! permutări în memorie ca o listă.
Acesta generează n! permutări dacă lungimea secvenței de intrare este n.
Dacă doriți să obțineți permutări ale lungimii L, atunci implementați-o în acest fel.
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)> |
>
>
Ieșire:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
Complexitatea de timp a acestui program este O(n^r) unde n este lungimea matricei de intrare și r este lungimea permutărilor care trebuie generate.
Complexitatea spațiului este, de asemenea, O(n^r), deoarece toate permutările sunt stocate în memorie înainte de imprimare.
Acesta generează nCr * r! permutări dacă lungimea secvenței de intrare este n și parametrul de intrare este r.
Combinaţie
Această metodă ia o listă și o intrare r ca intrare și returnează o listă de obiecte de tupluri care conțin toate combinațiile posibile de lungime r într-o formă de listă.
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)> |
>
>
Ieșire:
(1, 2) (1, 3) (2, 3)>
1. Combinațiile sunt emise în ordinea sortării lexicografice a intrării. Deci, dacă lista de intrare este sortată, tuplurile combinate vor fi produse în ordine sortată.
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)> |
>
>
Ieșire:
(1, 2) (1, 3) (2, 3)>
2. Elementele sunt tratate ca unice în funcție de poziție, nu de valoarea lor. Deci, dacă elementele de intrare sunt unice, nu vor exista valori repetate în fiecare combinație.
program python pentru căutare binară
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)> |
>
>
Ieșire:
(2, 1) (2, 3) (1, 3)>
3. Dacă vrem să facem o combinație a aceluiași element la același element atunci folosim combinații_cu_înlocuire.
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)> |
>
>
Ieșire:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>