在Python中递归地实现排列

我很抱歉已经有很多关于这个问题的文章。但是，我很难在自己的实施中看到自己的错误。所以我试图编写一个函数，它接受一个字符串并以列表的形式返回所有可能的排列。在Python中递归地实现排列

理论上应该是这样的：

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

来源

2013-05-15 Thalatta

我不确定你是否只是想练习，但如果你不是，itertools有一个方便的排列功能。例如， – James

，“你好”有2个“l”。因此，它会有双重排列。 – Drakosha

你将有重复排列如果您有重复的字母，因为这是你的逻辑做什么。

例如，'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或第二个。但是，如果你已经想好了，并且确保它是正确的，那么你应该只依靠这一点，并且可能会添加一条评论来解释为什么它是正确的。一般来说，不要这样做。

来源

2013-05-15 23:03:09 abarnert

请，走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-15 22:49:57

@Drakosha谢谢！我会删除这个，因为实际上没有错误。 – Thalatta

在Python中递归地实现排列

回答

相关问题