Пожалуйста, объясните этот алгоритм, чтобы получить все перестановки строки

Следующий код генерирует все перестановки для строки:

def permutations(word):
    if len(word)<=1:
        return [word]

    #get all permutations of length N-1
    perms=permutations(word[1:])
    char=word[0]
    result=[]
    #iterate over all permutations of length N-1
    for perm in perms:
        #insert the character into every possible location
        for i in range(len(perm)+1):
            result.append(perm[:i] + char + perm[i:])
    return result

Можете ли вы объяснить, как это работает? Я не понимаю рекурсии.

Ответы

Ответ 1

Алгоритм:

  • Удалить первую букву
  • Найти все перестановки оставшихся букв (рекурсивный шаг)
  • Вставьте письмо, которое было удалено во всех возможных местах.

Базовый регистр для рекурсии - это одна буква. Существует только один способ перестановки одной буквы.

Пример работы

Представьте, что начальное слово bar.

  • Сначала удалите b.
  • Найдите перестановки ar. Это дает ar и ra.
  • Для каждого из этих слов поставьте b в каждом месте:
    • ar → bar, abr, arb
    • ra → bra, rba, rab

Ответ 2

Я написал шаги для строки длиной 2 и строки длиной 3 ниже.

<сильные > перестановок ( 'аb')

len('ab') is not <= 1 
perms = permutations of 'b'
len('b') <= 1 so return 'b' in a list
perms = ['b']
char = 'a'
result = []
for 'b' in ['b']:
    for 0 in [0,1]:
        result.append('' + 'a' + 'b')
    for 1 in [0,1]:
        result.append('b' + 'a' + '')
result = ['ab', 'ba']

<сильные > перестановок ( 'ABC')

len('abc') is not <= 1
perms = permutations('bc')
perms = ['bc','cb']
char = 'a'
result =[]
for 'bc' in ['bc','cb']:
    for 0 in [0,1,2]:
        result.append('' + 'a' + 'bc')
    for 1 in [0,1,2]:
        result.append('b' + 'a' + 'c')
    for 2 in [0,1,2]:
        result.append('bc' + 'a' + '') 
for 'cb' in ['bc','cb']:
    for 0 in [0,1,2]:
        result.append('' + 'a' + 'cb')   
    for 1 in [0,1,2]:
        result.append('c' + 'a' + 'b')   
    for 2 in [0,1,2]:
        result.append('cb' + 'a' + '')
result = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']