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

Answer 1

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

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

Python - 递归字谜函数

Python - Recursive anagram function

recursion

anagram