CODEWITHSUNDEEP
pythonalgorithmpermutation
bb89
bb89

Reputation: 803

Could someone explain this python permutation code?

I've seen some postings of code for permutations on here but I haven't really been able to find a good step-by-step walk through of what is actually going on. If someone could just explain what is actually happening in each step of this code I would really appreciate it. I can't quite seem to wrap my head around it. The code I'm looking at is in Python and is from http://snippets.dzone.com/posts/show/753.

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]


for p in all_perms(['a','b','c']):
    print p

Upvotes: 3

Views: 1118

Answers (3)

Stephen Paulger
Stephen Paulger

Reputation: 5343

def all_perms(str):
    # If there is only one item, there can be only one permutation
    # yield the single item
    if len(str) <=1:
        yield str
    else:
        # loop over the permutations returned by a recursive call to all_perms
        # note it is passing a subset of the list passed in.
        for perm in all_perms(str[1:]):
            # for each returned sub-permutation insert the item that
            # wasn't passed into each possible position.
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]


for p in all_perms(['a','b','c']):
    print p

So you pass in ['a','b','c'].

It calls all_perms(['b', 'c']) and that calls all_perms(['c']) which yields 'c'.

the yield statement means that all_perms() is a generator the fact that it calls itself means it is using recursion.

I'd recommend using itertools.permutations rather than that snippet.

Upvotes: 2

Aaron Digulla
Aaron Digulla

Reputation: 328624

First of all, the name of the parameter str is a bad choice. It's probably due to the fact that it works for all kinds of sequence types in Phyton but it should be seq or something to make the intention clear.

  1. If the length of the list is <= 1 (empty or one element) return the list (there is just one solution for this case).

  2. For all other cases:

    a) Create all permutations of str[1:] (i.e. the list just without the head element).

    b) Insert the head element at each position in each permutation created in a) and return the result

yield works a bit like return; the main difference is that the current value is returned and, when the function is called again, it continues with the instruction after the yield.

This way, it's easy to assemble the result.

Example:

'a' gives 'a' (trivial). 'ab' first chops of the head ('a'), then creates all permutations of b (there is just one: 'b' itself). Now the head is inserted at every position, so we end up with 'ab' (head+list) and 'ba' (list+head).

etc.

Upvotes: 1

blubb
blubb

Reputation: 9900

What you see is a iterator generator. It's a function that returns an object which can be looped over.

during the execution of the for loop, all_perms is executed up to the point where it hits a yield. The value yielded is passed to the loop as p variable. Then the execution of all_perms is continued at the position after the yield statement where the method exited last time.

Upvotes: 1

Related Questions