Python Permutation Program Flow help
Question: i found this code at activestate, it takes a string and prints permutations of
the string. I understand that its a recursive function but i dont really
understand how it works, it'd be great if someone could walk me through the
program flow, thanks a bunch!

    
    
    import sys
    
    def printList(alist, blist=[]):
        if not len(alist): print ''.join(blist)
        for i in range(len(alist)):
            blist.append(alist.pop(i))
            printList(alist, blist)
            alist.insert(i, blist.pop())
    
    if __name__ == '__main__':
        k = 'love'
        if len(sys.argv) > 1: k = sys.argv[1]
        printList(list(k))
    


Answer: You can figure out how `printList` behaves by drawing a recursion tree. Each
node consists of two elements: an `alist` and a `blist`. The root has the
`alist` with the initial sequence of items you want to permute, and an empty
`blist`. Each node of the tree has one branch for each element of that node's
`alist`; you move from a 'father' node to each one of its 'children' by
choosing an element from the father's `alist` and:

  * assigning to the child's `alist` the father's `alist` _minus that element_ ;
  * assigning to the child's `blist` the father's `blist` plus that element _appended to its end_.

The leafs have an empty `alist`, and since following different paths from the
root to the leafs you have to choose elements from the root's `alist` in
different orders, the `blist` of the leafs themselves contain all the various
permutations of the root's `alist`.

For example (`[abc],[] == alist,blist`):

    
    
                               [abc],[] 
                             /     |     \
                           a/     b|      \c
                           /       |       \
                      [bc],[a]  [ac],[b]   [ab],[c]
                      /     \
                    b/       \c
                    /         \
               [c],[ab]      [b],[ac]
                  |             |
                 c|             |b
                  |             |
               [],[abc]      [],[acb]
    
    
    def printList(alist, blist=[]):
        # if alist is empty, we are in a 'leaf' in the recursion tree;
        # then blist contains one permutation; print it
        if not len(alist): print ''.join(blist)
    
        # ELSE, for each possible position in alist,
        for i in range(len(alist)):
    
            # move the element at that position from alist to the end of blist
            blist.append(alist.pop(i))
    
            # go to the 'children' node and do the printing job for its subtree
            printList(alist, blist)
    
            # then move back the element from the end of blist to its original
            # position in alist, so we can continue with the for loop
            # without altering alist
            alist.insert(i, blist.pop())
    

