3

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

理论上它应该是这样的：

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
4

2 回答 2

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)

除了对您已有的东西进行不必要的搜索这一明显的性能问题之外，如果您有任何重复的元素，它就不可能是正确的。例如，无论您尝试替换/查找/无论是第一个'l'还是'Hello'第二个，它都将始终替换第一个。

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

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

在这种特殊情况下，这并不重要，因为您实际上并不关心您是删除第一个l还是第二个。但是，只有在您仔细考虑并确保它是正确的情况下，您才应该依赖它——并且可能会添加一条评论来解释它为什么是正确的。一般来说，不要这样做。

于 2013-05-15T23:03:09.927 回答
2

请仔细查看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']
于 2013-05-15T22:49:57.567 回答