CODEWITHSUNDEEP
pythonalgorithmpermutation
edmamerto
edmamerto

Reputation: 8165

Permutation algorithm analysis

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!)?

Upvotes: 1

Views: 201

Answers (2)

PM 2Ring
PM 2Ring

Reputation: 55499

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.

Upvotes: 1

Mateus Zitelli
Mateus Zitelli

Reputation: 1302

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]

Upvotes: 3

Related Questions