我很抱歉已经有很多关于这个问题的帖子。但是,我很难看出我自己的实现哪里出了问题。所以我试图编写一个函数,它接受一个字符串并以列表的形式返回所有可能的排列。
理论上应该是这样的:
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
最佳答案
如果你有重复的字母,你就会有重复的排列,因为这就是你的逻辑。
例如,对于 '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
还是第二个。但是,只有在您仔细考虑并确保它是正确的情况下,您才应该依赖它——并且可能添加了一条注释来解释为什么它是正确的。一般来说,不要这样做。
关于python - Python中排列的递归实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16576231/