Q:

Recursive implementation of permutations in 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)...]
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!
Here is the Code:
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

A:

You're going to have duplicate permutations if you have duplicate letters, because that's what your logic does.
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'.
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)

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

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.
The right way to do this is with enumerate. For example:
for idx, i in enumerate(strng):
    smallerStr = strng[:idx] + strng[idx+1:]

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.

