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

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

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

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

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

但我真的不知道partials是如何生成的，我也不确定当word为空时，当我们不执行result.append('')时，解决方案是如何不起作用的。

魔法是如何运作的，有直观的解释吗？

Answer 1

这里有一个完整而冗长的答案。

简短的答案是，只有一种方法可以编写一个没有元素的序列。这是一个空序列。因此，具有''的所有排列的列表是['']。

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

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

奖金

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

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