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

# 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.

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)