Python Permutation Program Flow帮助

Question

我在activestate找到了这个代码,它需要一个字符串并打印字符串的排列.我知道它是一个递归函数,但我真的不明白它是如何工作的,如果有人可以引导我完成程序流程,那就太好了,谢谢你!

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

您可以printList通过绘制递归树来确定行为方式.每个节点由两个元素组成:a alist和a blist.根目录包含alist您要置换的项目的初始序列,并且为空blist.树的每个节点对于该节点的每个元素都有一个分支alist; 通过选择父亲的元素,你可以从'父'节点移动到每个'子节点',alist并且:

• 分配给孩子的alist父亲alist 减去那个元素 ;
• 分配给孩子的blist父亲blist加上附加到其末尾的元素.

叶子有一个空的alist,因为从根到叶子的不同路径你必须从alist不同的顺序中选择根的元素,blist叶子本身包含根的所有各种排列alist.

例如([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())