Python中置换的递归实现

Question

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

理论上应该是这样的：

allPermutations（“abc…z”）=[a+所有置换（b，c，…z），b+所有置换（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

Answer 1

如果你有重复的字母，你会有重复的排列，因为这就是你的逻辑所做的。在

例如，使用'Hello'，对于第一个l，为'Helo'的每个排列添加'l' + perm，然后对于第二个l，再次为'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

---

顺便说一句，你几乎不想做这样的事情：

^{2}$

…或

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

除了明显的性能问题，即不必要地搜索已有的内容之外，如果有任何重复的元素，就不可能是正确的。例如，无论您尝试替换'Hello'中的第一个'l'还是第二个，它都将始终替换第一个。在

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

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

在这个特定的例子中，这并不重要，因为您实际上并不关心您是删除第一个l还是第二个。但是，只有经过深思熟虑并确保它是正确的，并可能添加一条解释为什么是正确的注释时，才应该依赖于它。一般来说，就是不要这么做。在

Answer 2

请仔细查看itertools模块。只是这样：

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

一个例子：

^{2}$