Recursive implementation of permutations in Python

Question

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

I'm not sure if you're just trying to get practice, but if you're not, itertools has a handy permutations function. — James, May 15 '13 at 22:48
for example, "hello" has 2 "l"s. So it will have double permutations due to that. — Drakosha, May 15 '13 at 22:51

Saullo G. P. Castro · Answer 1 · 2013-08-06T05:19:32.063

2

Please, take a closer look in the itertools module. It will be just this:

import itertools
[ ''.join(i) for i in itertools.permutations(mystring) ]

One example:

[ ''.join(i) for i in itertools.permutations('abc')]
#['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

edited Aug 06 '13 at 05:19

answered May 15 '13 at 22:49

Saullo G. P. Castro

56,802
26
179
234

@Drakosha Thanks! I will be removing this, since there actually isn't an error. – Thalatta May 15 '13 at 23:02

score 2 · Accepted Answer · answered May 15 '13 at 23:03

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.

Recursive implementation of permutations in Python

2 Answers2

Linked