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
– Ed Heal, Commented May 20, 2018 at 3:23
It's actually a little worse than O(n!), A002627 gives the sequence: 1, 3, 10, 41, 206, 1237, 8660, ... — PM 2Ring
– PM 2Ring, Commented May 20, 2018 at 3: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
– PM 2Ring, Commented May 20, 2018 at 3:27
As for your 1st comment, bear in mind that each recursive call to permute gets its own fresh out list. — PM 2Ring
– PM 2Ring, Commented May 20, 2018 at 3: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
– Mark, Commented May 20, 2018 at 3:33

Mateus Zitelli · Accepted Answer · 2018-05-20 03:36:54Z

3

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]

edited May 20, 2018 at 3:36

answered May 20, 2018 at 3:30

Mateus Zitelli

1,3121 gold badge13 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

PM 2Ring · Accepted Answer · 2018-05-20 04:18:19Z

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.

Collectives™ on Stack Overflow

Permutation algorithm analysis

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related