Python надає прямі методи для пошуку перестановок і комбінацій послідовності. Ці методи присутні в пакеті itertools.
Перестановка
Спочатку імпортуйте пакет itertools для реалізації методу перестановок у python. Цей метод приймає список як вхідні дані та повертає список об’єктів кортежів, які містять усі перестановки у формі списку.
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)> |
>
>
Вихід:
як оновити java
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Часова складність: O(n!), де n - довжина вхідного списку. Це тому, що є n! перестановок n елементів, і програма генерує та друкує їх усі.
Допоміжні приміщення: O(n!), оскільки програма повинна зберігати всі n! перестановки в пам'яті, перш ніж їх роздрукувати. Зокрема, змінна perm, створена викликом permutations([1, 2, 3]), зберігає всі n! перестановки в пам'яті у вигляді списку.
Він породжує n! перестановок, якщо довжина вхідної послідовності дорівнює n.
Якщо ви хочете отримати перестановки довжини L, тоді реалізуйте це таким чином.
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)> |
>
>
Вихід:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
Часова складність цієї програми дорівнює O(n^r), де n — довжина вхідного масиву, а r — довжина перестановок, які мають бути згенеровані.
Складність простору також дорівнює O(n^r), оскільки всі перестановки зберігаються в пам’яті перед друком.
Він генерує nCr * r! перестановок, якщо довжина вхідної послідовності дорівнює n, а вхідний параметр дорівнює r.
Комбінація
Цей метод приймає список і вхід r як вхідні дані та повертає список об’єктів кортежів, які містять усі можливі комбінації довжини r у формі списку.
Python3
string.compareto c#
# 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)> |
>
>
Вихід:
(1, 2) (1, 3) (2, 3)>
1. Комбінації видаються в лексикографічному порядку введення. Отже, якщо вхідний список відсортовано, кортежі комбінацій будуть створені в відсортованому порядку.
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)> |
>
>
Вихід:
(1, 2) (1, 3) (2, 3)>
2. Елементи розглядаються як унікальні на основі їхньої позиції, а не їх значення. Отже, якщо вхідні елементи унікальні, у кожній комбінації не буде повторюваних значень.
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)> |
>
>
Вихід:
(2, 1) (2, 3) (1, 3)>
3. Якщо ми хочемо створити комбінацію того самого елемента з тим самим елементом, ми використовуємо комбінації_із_заміною.
cdr повна форма
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)> |
>
>
Вихід:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>