Python -递归anagram函数

Question

我正在做一项家庭作业，我有点卡住了，需要一些帮助。

我不想把答案交给我，但如果我能得到一些帮助或提示，我会非常感激。

我必须创建一个anagram生成器，它只进行1次递归函数调用，没有for循环。

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"的位置。如果你能使用理解，你就可以很容易地做到这一点。如果你不能，那么.每个循环都可以重写成递归，所以...让我再想一想。