Could someone explain this python permutation code?

Question

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

Stephen Paulger · Accepted Answer · 2011-03-25 16:54:27Z

2

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.

answered Mar 25, 2011 at 16:54

Stephen Paulger

5,3733 gold badges31 silver badges46 bronze badges

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

1 Comment

bb89 Over a year ago

Thank you, this was very helpful. I knew about itertools.permutations but I really just wanted to have a better understanding of what was going on in the code I posted. Thanks again!

Aaron Digulla · Accepted Answer · 2011-03-25 16:49:27Z

1

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.

If the length of the list is <= 1 (empty or one element) return the list (there is just one solution for this case).
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.

answered Mar 25, 2011 at 16:49

Aaron Digulla

330k111 gold badges626 silver badges840 bronze badges

2 Comments

bb89 Over a year ago

Thank you! This is what I was looking for. The combination of the yield and recursion made it tough for me to grasp at first, but it makes sense now. And I know what you're saying about the str variable. Had I written it I wouldn't have named it that either, but I just grabbed it from the site I mentioned in my original post. Thanks again!

Aaron Digulla Over a year ago

It's astonishing how much more simple some code can become when you give variables the proper names; that's why I mentioned it.

blubb · Accepted Answer · 2011-03-25 16:45:47Z

1

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.

answered Mar 25, 2011 at 16:45

blubb

10k3 gold badges45 silver badges90 bronze badges

Collectives™ on Stack Overflow

Could someone explain this python permutation code?

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related