Python 置换程序流程帮助

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通过绘制递归树来表现。每个节点由两个元素组成:alist和一个 blist .根有 alist包含您要排列的项目的初始序列，以及一个空的 blist .树的每个节点对于该节点的 alist 的每个元素都有一个分支;您通过从父亲的 alist 中选择一个元素，从“父亲”节点移动到它的每个“ child ”节点和:

• 分配给 child 的 alist父亲的alist 减去那个元素;
• 分配给 child 的 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())