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

14

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

def permutations(word):
    if len(word)
Похоже, у вас есть ошибка отступа, также, этоСтоит отметить, что этот код заново изобретает колесо. Там'ужеitertools.permutations в стандартной библиотеке :-) - Хотя это нене поможет вам понять этот код. mgilson
@DavidRobinson Я думаю, это было простомилый" способ узнать, что происходит в коде. Я'Мы переписали вопрос, чтобы напрямую спросить объяснение, которое, как мне кажется, было тем, что спрашивающий хотел (и получил). Blckknght
Что вы подразумеваете под "он" а также "этот мужчина"? David Robinson

Ваш Ответ

2   ответа
7

Перестановки (»а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'] 

Перестановки (»а ')

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']  
53

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

Базовый случай для рекурсии - одна буква. Есть только один способ переставить одну букву.

Работал пример

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

Сначала удалите.bНайти перестановкиar, Это даетar а также .raДля каждого из этих слов поставьтеb в каждом месте: ->ar , ->barabrarbra Яbrarbarab

Похожие вопросы