Python Permutation Program Flow help

Question

Hello world, 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

To understand it clearly remove the loop with alist=love and blist initialized to []: The 4 printlist calls in the for loop will now be(at first level of recursion):

   printList("ove","l");
   printList("lve","o");
   printList("loe","v");
   printList("lov","e");

Each of these printList calls has bList initialized to all possible permutations of one lettered lists, and alist has the remaining 3 letters. This is will continue until alist becomes empty and all the letters are in blist (and the printing happens if not len(alist): print ''.join(blist))

In the second level of recursion for example

   printList("ove","l") will result in 3 calls

   printList("ve","lo");
   printList("oe","lv");
   printList("ov","le");

Total permutations = 4(firstlevel) * 3(2nd level) * 2 * 1

Answer 2

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

Answer 3

Shameless plug - Here is an elementary permutation code in python along with explanation from my blog. Playing with recursion - string permutation