Explain Python code for listing all permutations

Question

class Permutation:
    def __init__(self,justalist):
        self._data = justalist[:]
        self._sofar = []
    def __iter__(self):
        return self.next()
    def next(self):
        for elem in self._data:
            if elem not in self._sofar:
                self._sofar.append(elem)
                if len(self._sofar) == len(self._data):
                    yield self._sofar[:]
                else:
                    for v in self.next():
                        yield v
                self._sofar.pop()

Found this code online ( http://users.softlab.ntua.gr/~ttsiod/yield.html ). Tried to figure it out, but haven't made much headway. The part that is really tripping me up is the:

                 for v in self.next():
                    yield v
                 self._sofar.pop()

To code for the class is run by doing:

      for i in Permutation(a):
         print(i)

I've read this:

"by invoking yield, the next member is now a generator function, so we can't just simply call next again - if we did, we would lose the returned generator object, and thus, the returned permutations! We must instead loop over the returned results with a simple for v in self.next(): yield v. This way, the results are properly propagated to the "parent" call."

I don't know if this explains what is going on, but it means nothing to me. (I thought I understood generators.)

Answer 1

This class is a generator that recursively calls itself (self.next()).

It is a bit odd, because when you ask the generator for all its values, it doesn't really follow the iteration protocol by returning self (an object with a .next() function) like you'd expect. Rather, it returns the result of self.next(), which is quite poor wording. The next function should rather just be called permutations(), because the next function really has nothing whatsoever to do with the fact that a next function is required in the iteration protocol.

Anyway, you can see the recursive trace of this if you augment the function with a recursion depth parameter:

class Permutation:
    def __init__(self,justalist):
        self._data = justalist[:]
        self._sofar = []
    def __iter__(self):
        return self.next()
    def next(self, depth=0):
        debug = lambda text:print('\t'*depth+' '+text)
        for elem in self._data:
            #print( 'self._data: {}'.format(self._data) )
            #print( 'self._sofar: {}'.format(self._sofar) )
            if elem not in self._sofar:
                self._sofar.append(elem)
                if len(self._sofar) == len(self._data):
                    debug( 'yielding self._sofar[:]: {}'.format(self._sofar[:]) )
                    yield self._sofar[:]
                else:
                    for v in self.next(depth+1):
                        debug( 'yielding elements of self.next() one-by-one: {}'.format(v) )
                        yield v
                self._sofar.pop()

Demo:

>>> list( Permutation(range(4)) )
                         yielding self._sofar[:]: [0, 1, 2, 3]
                 yielding elements of self.next() one-by-one: [0, 1, 2, 3]
         yielding elements of self.next() one-by-one: [0, 1, 2, 3]
 yielding elements of self.next() one-by-one: [0, 1, 2, 3]
                         yielding self._sofar[:]: [0, 1, 3, 2]
                 yielding elements of self.next() one-by-one: [0, 1, 3, 2]
         yielding elements of self.next() one-by-one: [0, 1, 3, 2]
 yielding elements of self.next() one-by-one: [0, 1, 3, 2]
                         yielding self._sofar[:]: [0, 2, 1, 3]
                 yielding elements of self.next() one-by-one: [0, 2, 1, 3]
         yielding elements of self.next() one-by-one: [0, 2, 1, 3]
 yielding elements of self.next() one-by-one: [0, 2, 1, 3]
                         yielding self._sofar[:]: [0, 2, 3, 1]
                 yielding elements of self.next() one-by-one: [0, 2, 3, 1]
         yielding elements of self.next() one-by-one: [0, 2, 3, 1]
 yielding elements of self.next() one-by-one: [0, 2, 3, 1]
                         yielding self._sofar[:]: [0, 3, 1, 2]
                 yielding elements of self.next() one-by-one: [0, 3, 1, 2]
         yielding elements of self.next() one-by-one: [0, 3, 1, 2]
 yielding elements of self.next() one-by-one: [0, 3, 1, 2]
                         yielding self._sofar[:]: [0, 3, 2, 1]
                 yielding elements of self.next() one-by-one: [0, 3, 2, 1]
         yielding elements of self.next() one-by-one: [0, 3, 2, 1]
 yielding elements of self.next() one-by-one: [0, 3, 2, 1]
                         yielding self._sofar[:]: [1, 0, 2, 3]
                 yielding elements of self.next() one-by-one: [1, 0, 2, 3]
         yielding elements of self.next() one-by-one: [1, 0, 2, 3]
 yielding elements of self.next() one-by-one: [1, 0, 2, 3]

As you can see, the flow of the data is as follows: recursion proceeds to the deepest level (4 in this case, len([0,1,2,3]) is 4), produces a permutation, and yields it back up to the previous level. That level yields it back up to the previous level, etc. At the highest level, the yield returns it.

In conclusion, this is a broken and terrible implementation, since:

1. It could just be accomplished by a recursive functional pattern with this extra Class nonsense
2. It defines next() in a way that strongly implies something, but actually does something else.
3. It will fail if any values are duplicated, e.g. Permutation([0,1,1]) will fail

You should just use http://docs.python.org/library/itertools.html#itertools.permutations (from itertools import permutations)

Answer 2

The key idea is that Permutation.next() yields all permutations of the items in _data that begin with _sofar.

To do this, we try adding on each possible element onto the end of _sofar. There are then two cases: either _sofar is long enough (i.e., we've got a complete permutation), in which case we just yield a copy of it; or it isn't (i.e., we've got a partial permutation), in which case we recursively call next -- which, in general, yields lots of permutations, so we have to yield them on ourselves one by one.

Incidentally, I think the code would be neater and easier to understand if it went more like this (DANGER: untested code):

def next(self):
    if len(self._sofar) == len(self._data):
        yield self._sofar[:]
    else:
        for elem in self._data:
            if elem not in self._sofar:
                self._sofar.append(elem)
                for v in self.next():
                    yield v
                self._sofar.pop()

which also has the merit of giving the right answer when there are no elements (there's exactly one permutation, the empty sequence; the code as given yields none). There are a few optimizations I'd be inclined to make, too, but they aren't important.