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 1

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())