Python中置换的递归实现

问题描述

很抱歉，已经有很多关于此问题的帖子.但是，我很难知道自己的实现中哪里出了问题.因此，我试图编写一个接受字符串并以列表形式返回所有可能排列的函数.

I apologize that there have already been many posts about this problem. However, I am having a hard time seeing where I am going wrong in my own implementation. So I am trying to write a function that takes in a string and returns all of it's possible permutations in the form of a list.

理论上，它应如下所示:

Theoretically it should look like this:

allPermutations("abc ... z")= [a + allPermutations(b，c，... z)，b + allPermutations(a，c ... z)...]

allPermutations("abc...z") = [a + allPermutations(b,c,...z), b + allPermutations(a,c...z)...]

我当前的实现在对字符串"Hello"进行测试时，会输出一堆重复的排列.谁能帮我看看我要去哪里错了.感谢您的协助！

My current implementation, when tested on the String, "Hello", outputs a bunch of duplicate permutations. Can anyone help me see where I am going wrong. I appreciate your assistance!

这是代码:

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

推荐答案

如果字母重复，您将有重复的排列，因为这就是您的逻辑.

You're going to have duplicate permutations if you have duplicate letters, because that's what your logic does.

例如，使用'Hello'，对于第一个l，您要为'Helo'的每个排列添加'l' + perm，然后对于第二个l，您又是 为'Helo'的每个排列添加'l' + perm.

For example, with 'Hello', for the first l, you're adding 'l' + perm for each permutation of 'Helo', and then for the second l, you're again adding 'l' + perm for each permutation of 'Helo'.

有几种方法可以显示没有重复的排列.最简单的方法是循环遍历set(strng)而不是strng:

There are a few ways you can show permutations without duplicates. The simplest is to just loop over set(strng) instead of 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

---

作为旁注，您几乎永远都不想做这样的事情:

---

As a side note, you almost never want to do anything like this:

for i in strng:
    smallerStr = strng.replace(i,"",1)

…或

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

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

Besides the obvious performance problem of an unnecessary search for something you already have, there's no way it can be correct if you have any duplicate elements. For example, whether you try to replace/find/whatever the first 'l' in 'Hello' or the second, it will always replace the first one.

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

The right way to do this is with enumerate. For example:

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

在这种特殊情况下，它并不重要，因为您实际上并不关心要删除第一个l还是第二个l.但是，只有经过深思熟虑并确保它正确无误，您才可以依靠它，并且可以添加注释以解释它为什么正确.通常，不要这样做.

In this particular case, it happens to not matter, because you don't actually care whether you're removing the first l or the second one. But you should only rely on that if you've thought it through and made sure it's correct—and maybe added a comment explaining why it's correct. In general, just don't do it.

这篇关于Python中置换的递归实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！