Permutation algorithm analysis

Question

I've been studying algorithms like crazy for a big interview. This particular algorithm is driving me crazy I've added comments to some lines that don't understand.

def permute(s):
    out = []

    if len(s) == 1:
        # wouldn't setting out replace everything in out?
        out = [s]

    else:
        for i, let in enumerate(s):

            # how does it know that I only want 2 strings?
            for perm in permute(s[:i] + s[i+1:]):

                out += [let + perm]

    return out

print permute("cat")

Is it correct to say that the time complexity of this algorithm is O(n!)?

As an aside - In an interview the interviewer does not usually care if you get the correct answer. What they are trying to find out how you approach a problem. — Ed Heal, May 20 '18 at 03:23
It's actually a little worse than O(n!), [A002627](https://oeis.org/A002627) gives the sequence: 1, 3, 10, 41, 206, 1237, 8660, ... — PM 2Ring, May 20 '18 at 03:25
I don't get this comment: "# how does it know that I only want 2 strings?" `s[:i] + s[i+1:]` creates a single string which is a copy of `s` with the char at index `i` removed. — PM 2Ring, May 20 '18 at 03:27
As for your 1st comment, bear in mind that each recursive call to `permute` gets its own fresh `out` list. — PM 2Ring, May 20 '18 at 03:30
I would actually change `out = [s]` to `return [s]`. It's a base case and returning directly from it seems clearer to me. — Mark, May 20 '18 at 03:33

Mateus Zitelli · Accepted Answer · 2018-05-20T03:36:54.450

Initially out is defined inside the context of the permute method, so each call will have its own out vector. So when redefining out = [s] you just overriding the out=[] inside the method context.

If the input is bigger than one char this is what happens:

# Iterate for each char
for i, let in enumerate(s):
    # Iterate for each permutation of the string without the char i
    for perm in permute(s[:i] + s[i+1:]):
            # Put the removed char in the beginning of the permutation
            # and add it to the list.
            out += [let + perm]

score 1 · Answer 2 · answered May 20 '18 at 04:18

Just for fun, here's a generator version of that algorithm. It's a bit nicer because it doesn't require those out lists.

def permute(s):
    if len(s) == 1:
        yield s
    else:
        for i, let in enumerate(s):
            for perm in permute(s[:i] + s[i+1:]):
                yield let + perm

for s in permute("abc"):
    print(s)

output

abc
acb
bac
bca
cab
cba

Of course, it's almost always better to avoid recursion (especially in Python) unless the problem needs recursion (eg processing recursive data structure, like trees). And of course a real Python program would normally use itertools.permutations, unless it needs to correctly handle repeating items in the base sequence. In that case, I recommend the iterative algorithm of Narayana Pandita, as shown in this answer.

Permutation algorithm analysis

2 Answers2