python - 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

Answer 1

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

例如，对于 '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 还是第二个。但是，只有在您仔细考虑并确保它是正确的情况下，您才应该依赖它——并且可能添加了一条注释来解释为什么它是正确的。一般来说，不要这样做。