Python udostępnia bezpośrednie metody znajdowania permutacji i kombinacji sekwencji. Metody te są obecne w pakiecie itertools.
Permutacja
Najpierw zaimportuj pakiet itertools, aby zaimplementować metodę permutacji w Pythonie. Ta metoda przyjmuje listę jako dane wejściowe i zwraca listę obiektów zawierającą krotki zawierające wszystkie permutacje w formie listy.
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)> |
>
>
Wyjście:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Złożoność czasowa: O(n!), gdzie n jest długością listy wejściowej. Dzieje się tak, ponieważ istnieje n! permutacje n elementów, a program generuje i drukuje je wszystkie.
Przestrzeń pomocnicza: O(n!), ponieważ program musi przechowywać wszystkie n! permutacje w pamięci przed ich wydrukowaniem. W szczególności zmienna perm utworzona przez wywołanie permutacji ([1, 2, 3]) przechowuje wszystkie n! permutacje w pamięci jako lista.
Generuje n! permutacje, jeśli długość sekwencji wejściowej wynosi n.
Jeśli chcesz uzyskać permutacje długości L, zaimplementuj to w ten sposób.
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)> |
komputer wynalazł, w którym roku
>
>
Wyjście:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
Złożoność czasowa tego programu wynosi O(n^r), gdzie n jest długością tablicy wejściowej, a r jest długością generowanych permutacji.
Złożoność przestrzenna wynosi również O(n^r), ponieważ wszystkie permutacje są przechowywane w pamięci przed wydrukowaniem.
Generuje nCr*r! permutacje, jeśli długość sekwencji wejściowej wynosi n, a parametrem wejściowym jest r.
Połączenie
Ta metoda przyjmuje listę i dane wejściowe r jako dane wejściowe i zwraca listę obiektów krotek, które zawierają wszystkie możliwe kombinacje długości r w formie listy.
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)> |
>
>
Wyjście:
(1, 2) (1, 3) (2, 3)>
1. Kombinacje są emitowane w porządku leksykograficznym. Tak więc, jeśli lista wejściowa jest posortowana, krotki kombinacji zostaną utworzone w posortowanej kolejności.
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)> |
>
>
Wyjście:
(1, 2) (1, 3) (2, 3)>
2. Elementy są traktowane jako unikalne na podstawie ich pozycji, a nie wartości. Jeśli więc elementy wejściowe są unikalne, w każdej kombinacji nie będzie powtarzających się wartości.
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)> |
>
>
Wyjście:
(2, 1) (2, 3) (1, 3)>
3. Jeżeli chcemy wykonać kombinację tego samego elementu z tym samym elementem to używamy kombinacji_z_zamianą.
Python3
sortowanie tablicowe Java
# 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)> |
>
>
Wyjście:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>