Python - рекурсивная функция анаграммы

Question

Я работаю над домашним заданием, немного застрял и могу помочь, пожалуйста.

Я не хочу, чтобы ответ был вручен мне, но если бы я мог получить некоторую помощь или советы, я был бы очень признателен.

Мне нужно создать генератор анаграмм, который делает только 1 рекурсивный вызов функции, но не для циклов.

def anagram(st): 
if len(st) == 0:
    return []
else:
    if len(st) > 1:
        print(st)
        return [st] + [st[0]] + anagram(st[1:])
    else:
        print("test2",st)
        return [st[1:] + st[0]]

ana = anagram('abc') 

Это мои результаты: ['abc', 'a', 'bc', 'b', 'c'] 5

Ответ должен быть следующим: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] 6

Answer 1

Давайте немного подумаем без кода, начиная с общего случая. Скажем, вы уже знаете перестановки "bc", а они ["bc", "cb"]. Как вы добавляете "a" к смеси? Я бы взял каждый из сгенерированных элементов и вставил a в каждую позицию. Итак, возьмите "bc" и, вставив "a" в каждую позицию, вы получите ["abc", "bac", "bca"]. Затем сделайте то же самое с "cb". Это приводит нас к базовому случаю: поскольку каждая рекурсия умножает количество результатов, число результатов в базовом случае должно быть 1, а не 0, потому что, когда мы перебираем решения предыдущего уровня, вы не сможете добавить ничего, так как там ничего нет. Таким образом, anagrams("") должен возвращать [""] (чтобы при вставке "c" позже он помещался в единственную позицию, которую он может).

К сожалению, это уже два цикла, о которых мы говорим (даже с общей рекурсивной природой алгоритма): один, который перебирает ["cb", "bc"], и другой, который перебирает позиции для вставки "a". Если вы можете использовать понимание, вы можете сделать это довольно легко. Если вы не можете, ну ... каждый цикл можно переписать в рекурсию, так что ... позвольте мне подумать немного подробнее.