python - Python - 递归字谜函数

Question

我正在做家庭作业，有点卡住了，请帮忙。

我不希望将答案交给我，但如果我能得到一些帮助或提示，我将不胜感激。

我必须创建一个字谜生成器，它只进行 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

标签： pythonrecursionanagram

Answer 1

让我们考虑一下没有代码的情况，从一般情况开始。假设您已经知道 的排列"bc"，它们是["bc", "cb"]。你如何添加"a"到混合物中？我会采用到目前为止生成的每个元素，并插入a每个位置。所以，取，并在每个位置"bc"插入，你会得到。然后对. 这将我们引向基本情况：由于每次递归都会乘以结果的数量，因此基本情况中的结果数量必须为 1，而不是 0，因为当我们迭代上一级的解决方案时，您将无法追加什么都没有，因为什么都没有。因此，必须返回（以便稍后插入将其放入唯一可以使用的位置）。"a"["abc", "bac", "bca"]"cb"anagrams("")[""]"c"

不幸的是，这已经是我们正在谈论的两个循环（即使具有算法的一般递归性质）：一个循环遍历["cb", "bc"]，一个循环遍历要插入的位置"a"。如果你可以使用推导式，你就可以很容易地做到这一点。如果你不能，那么......每个循环都可以重写为递归，所以......让我再想一想。