Python中排列的递归实现

Question

很抱歉，关于这个问题已经有很多帖子了。然而，我自己的实现中却很难看出我的错误所在。因此，我正在尝试编写一个函数，它接受一个字符串并以列表形式返回所有可能的排列。

理论上它应该像这样：

allPermutations("abc...z") = [a + allPermutations(b,c,...z), b + allPermutations(a,c...z)...]

我的当前实现，在测试字符串"Hello"时输出了许多重复的排列。有人能帮我看看我哪里出错了吗？感谢您的帮助！

以下是代码：

def allPermutations(strng):
    if len(strng) ==1:
        return [strng]
    perm_list = []
    for i in strng:
        smallerStr = strng.replace(i,"",1)
        z = allPermutations(smallerStr)

        for t in z:
            perm_list.append(i+t)        
    return perm_list

- Thalatta

---

我不确定你是不是只是在练习，但如果不是的话，itertools有一个方便的排列函数。 - James

例如，"hello" 有2个 "l"，因此它的排列组合将会加倍。 - Drakosha

Answer 1

请仔细查看 itertools 模块。只需要这样做：

import itertools
[ ''.join(i) for i in itertools.permutations(mystring) ]

一个例子：

[ ''.join(i) for i in itertools.permutations('abc')]
#['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

- Saullo G. P. Castro

---

@Drakosha 谢谢！我会将其删除，因为实际上没有错误。 - Thalatta

Answer 2

如果存在重复的字母，你会得到重复的排列，因为这就是你的逻辑所做的事情。

例如，对于 'Hello'，对于第一个 'l'，你要添加 'l' + perm 作为 'Helo' 的每个排列，然后对于第二个 'l'，你又要添加 'l' + perm 作为 'Helo' 的每个排列。

有几种方法可以显示没有重复的排列。最简单的方法就是循环遍历 set(strng) 而不是 strng:

def allPermutations(strng):
    if len(strng) ==1:
        return [strng]
    perm_list = []
    for i in set(strng):
        smallerStr = strng.replace(i,"",1)
        z = allPermutations(smallerStr)

        for t in z:
            perm_list.append(i+t)        
    return perm_list

作为一个附注，你几乎不想做这样的事情：

for i in strng:
    smallerStr = strng.replace(i,"",1)

… 或者

for x in lst:
    idx = lst.find(x)

除了明显的性能问题——不必要地搜索您已经拥有的内容，如果您有任何重复的元素，则无法正确查找。例如，无论您尝试在'Hello'中替换/查找/执行任何操作的第一个'l'还是第二个，它总是会替换第一个。

正确的方法是使用enumerate。例如：

for idx, i in enumerate(strng):
    smallerStr = strng[:idx] + strng[idx+1:]

在这种情况下，这并不重要，因为您实际上并不关心是删除第一个l还是第二个。但如果您经过深思熟虑并确保其正确，可能会添加一条解释为什么它是正确的评论。总的来说，最好不要这样做。

- abarnert