python - 我的递归生成字符串的所有排列的解决方案如何工作？

Question

def permutationString(word):
    print('word', word)
    result = []

    if len(word) == 0:
        result.append('')
        return result

    for i in range(len(word)):
        before = word[0 : i]
        after = word[i + 1 :]
        print('before',before)
        print('after', after)
        partials = permutationString(before + after)
        print(partials)
        for s in partials:
            result.append(word[i] + s)

    return result

这是我为给定字符串生成排列的解决方案。

对于 input abc，它给了我['abc', 'acb', 'bac', 'bca', 'cab', 'cba']这似乎是正确的。

我的问题是，我真的不明白魔法是如何运作的。代码本身非常直观；我们只是尝试将每个字符作为第一个字符，然后附加排列。

但我真的不明白它partials是如何生成的，我不确定当我们不这样做result.append('')时解决方案是如何工作的word。

是否有关于魔法如何运作的直观解释？

标签： pythonrecursionpermutation

Answer 1

我在这里有一个完整的答案。

较短的答案是只有一种方法可以编写没有元素的序列。那是空序列。所以具有 的所有排列的列表''是 ['']。

假设你弄错了然后返回[]，也就是说，没有解决方案。那时会发生什么？

好吧，在归纳的情况下，正如您所说，您尝试将每个元素作为第一个元素，并将其放在没有该元素的排列解决方案的前面。所以考虑一个只有一个元素的序列'x'。你将把x所有解决方案放在前面''。''如果返回的排列[]是一个没有解决方案的空列表，那么您将没有解决方案可以放在x前面。但是它会返回['']，因此您将放在'x'那个解决方案的前面''。

奖金

一旦你认为你明白了，你可能想尝试另一种类似的算法来计算排列。

尝试构建在每个递归步骤中word仅选择第一个元素的所有排列word[0]，并以某种方式将其与排列的解决方案“组合” word[1:]。