Все перестановки строки

Перестановка — это способ упорядочить элементы множества в разном порядке. Например, символы строки yup можно расставить семью способами: yup, ypu, uyp, upy, puy, pyu (и вариант «ничего не выбирать»).

В этой статье разберём два способа сгенерировать все перестановки: рекурсивный и с помощью стандартного модуля itertools.

Что нужно знать

Перед изучением примера полезно понимать:

Python: строки — строки в Python
Python: цикл for — цикл for
Оператор if…else в Python — условный оператор if...else

Пример 1. Рекурсия

def get_permutation(string, i=0):

    if i == len(string):
        print("".join(string))

    for j in range(i, len(string)):

        words = [c for c in string]

        # swap
        words[i], words[j] = words[j], words[i]

        get_permutation(words, i + 1)

print(get_permutation('yup'))

Вывод

yup
ypu
uyp
upy
puy
pyu
None

В этом примере используется рекурсия, чтобы получить все перестановки строки yup.

Условие if печатает строку, переданную в функцию, когда индекс i совпадает с её длиной.
На каждой итерации цикла for символы строки копируются в список words.
Элементы списка меняются местами — так получаются разные комбинации.
Процесс продолжается, пока не будет достигнута максимальная глубина.

Пример 2. Модуль itertools

from itertools import permutations

words = [''.join(p) for p in permutations('pro')]

print(words)

Вывод

['pro', 'por', 'rpo', 'rop', 'opr', 'orp']

Функция permutations из модуля itertools сама генерирует все перестановки строки. С помощью спискового включения мы склеиваем кортежи символов обратно в строки.