Python: Найдите все перестановки строки (3 легких способа!)

В этом руководстве вы узнаете, как использовать Python для поиска всех перестановок строки, включая использование itertools, рекурсии и циклов for в Python. Вы также узнаете, как найти все комбинации строки, когда допускается замена отдельных букв.

Но что такое перестановка? Перестановка - это различное упорядочивание элемента. Например, строка abc может быть записана как ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'].

Содержание

• Что такое перестановки строки?

• Использование Itertools в Python для поиска всех перестановок строки

• Использование рекурсии в Python для поиска всех перестановок строки

• Перестановки с повторениями строки в Python

• Заключение

Что такое перестановки строки?

Перестановки строки относятся ко всем различным порядкам, которые может принимать строка. Давайте, например, рассмотрим строку из трех букв: 'abc'. Когда мы находим все перестановки этой строки, мы получаем следующий список: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']. Здесь мы видим, что у нас есть список, содержащий шесть элементов.

Мы можем фактически вычислить количество перестановок, которое будет иметь строка любой длины, вычислив факториал ее длины. Так, в нашем примере с 'abc' мы вычислим значение 3!, которое фактически равно 3x2x1 = 6.

Теперь, когда у вас есть понимание того, что значит генерировать все комбинации строки в Python, давайте посмотрим, как мы можем легко генерировать различные перестановки строки.

Использование Itertools в Python для поиска всех перестановок строки

Itertools - это фантастический встроенный инструмент Python, который позволяет легко работать с задачами, связанными с итерируемыми объектами. Верите вы или нет, но строки в Python являются итерируемыми объектами! Благодаря этому мы можем легко итерировать по нашим строкам, используя библиотеку itertools.

Фактически, в библиотеке itertools есть функция под названием permutations. Когда мы передаем в нее итерируемый объект, в данном случае строку, функция возвращает список всех возможных комбинаций.

Давайте рассмотрим наш пример строки и как мы можем использовать библиотеку itertools для вычисления ее перестановок:

# Использование itertools для поиска всех перестановок строки
import itertools

a_string = 'abc'
string_permutations = itertools.permutations(a_string)
string_permutations = list(string_permutations)
string_permutations = [''.join(permutation) for permutation in string_permutations]

print(string_permutations)

# Возвращает: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Давайте рассмотрим, что мы здесь сделали:

• Импортировали библиотеку itertools

• Загрузили нашу строку и присвоили ее переменной a_string

• Затем использовали функцию permutations() для создания объекта itertools

• Преобразовали этот объект в список, который вернул список кортежей, содержащих наши перестановки

• Наконец, использовали списковое включение для объединения наших перестановок в отдельные строки

В следующем разделе вы узнаете, как использовать рекурсию для поиска комбинаций строки в Python.

Использование рекурсии в Python для поиска всех перестановок строки

Концепция, которую мы будем использовать в рекурсии для создания перестановок, известна как backtracking (возврат). Идея заключается в том, что мы возвращаемся назад для каждой возможной комбинации, которая может существовать.

Давайте посмотрим, как этот рекурсивный метод работает для поиска всех комбинаций строки в Python:

# Получение всех перестановок строки с помощью рекурсии в Python
a_string = 'abc'

def get_permutation(some_string, idx=0):

    if idx == len(some_string) - 1:   	 
        print("".join(some_string))

    for j in range(idx, len(some_string)):
        words_list = [c for c in some_string]   
        words_list[idx], words_list[j] = words_list[j], words_list[idx]
   	 
        get_permutation(words_list, idx + 1)

permutations = get_permutation(a_string)
print(permutations)

# Возвращает: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Мы видим, что это возвращает то же самое, что и выше. Однако, для начинающих пользователей Python этот метод немного менее интуитивно понятен, поэтому, возможно, использование метода itertools будет предпочтительнее для читаемости. Этот метод, однако, полезен, когда вы по какой-то причине не можете использовать itertools.

Хотите узнать, как использовать функцию Python zip() для итерации по двум спискам? Это руководство точно объясняет, что делает функция zip() и показывает некоторые творческие способы использования функции.

Перестановки с повторениями строки в Python

В приведенных выше примерах мы использовали Python для поиска всех комбинаций строки без повторений. В этом разделе вы узнаете, как использовать Python для получения всех перестановок строки с повторениями.

Это можно легко сделать с помощью цикла for в Python.

Давайте рассмотрим пример, используя ту же строку, что и раньше, 'abc':

# Использование Python для получения всех комбинаций строки с повторениями
a_string = 'abc'

final_list = [[]]
length = len(a_string)
groups = [list(a_string)] * length
for i in groups:
    final_list = [x+[y] for x in final_list for y in i]

permutations = [''.join(item) for item in final_list]
print(permutations)

# Возвращает ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

В коде выше мы используем цикл for и списковое включение для возврата всех комбинаций строки Python с повторениями.

Приведенный выше код может быть довольно ресурсоемким. Мы также можем видеть здесь, что у нас гораздо больше комбинаций, когда мы используем повторения, чем если бы мы их не использовали.

Заключение

В этой статье вы узнали, как использовать Python для создания списка всех перестановок строки. Вы узнали, как это делать с помощью популярной библиотеки itertools, а также с помощью рекурсии. Затем вы узнали, как использовать цикл for в Python для создания списка всех комбинаций строки, когда разрешены повторения.

Чтобы узнать больше о функции permutation(), ознакомьтесь с официальной документацией.