python - 帮助理解这个递归 python 函数是如何工作的？

Question

我是一名程序员，我会使用 C# perl 和 python，无论如何，我发现这个递归代码可以生成符号和字母列表的排列，但我不知道它是如何工作的？谁能解释一下？

#!/usr/bin/env python
#-*- coding:utf-8 -*-

def generate(charlist,state,position):
    for i in charlist:
        state[position] = i
        if position == (len(state)-1):
            print "".join(state)
        else:
            generate(charlist,state,position+1)

generate("1234567890qwertyuiopasdfghjklzxcvbnm",[None]*8,0)

这是代码，所有间距都正确。

Answer 1

这不会生成排列。它生成 n 维笛卡尔积。 (在此过程中，它也会生成所有排列，但生成仅排列的算法会有所不同。)

要解释它是如何工作的有点困难，但如果你查看小输入的输出，你就会明白发生了什么。考虑 'abc' 和 [None] * 3 的输出(我修改了代码以充当真正的生成器):

>>> def generate(charlist,state,position):
...     for i in charlist:
...         state[position] = i
...         if position == (len(state)-1):
...             yield "".join(state)
...         else:
...             for j in generate(charlist,state,position+1):
...                 yield j
... 
>>> print list(generate('abc', [None] * 3, 0))
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 
 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 
 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

如您所见，最初 generate 调用自身三次，每次递增 position(从 0 到 1 到 2)。每次通过递归循环，它都会将 'a' 放在当前位置并测试它是否已到达 state 列表的末尾。如果是这样，它会产生结果并且不会调用自己。

在这种情况下，当发生这种情况时，position == 2。现在 for 循环开始，将 'b' 和 'c' 存储在 state[2] 中并产生这些州中的每一个。然后函数结束，控制权返回给调用者，position == 1。然后调用者继续执行它的 for 循环；它设置 state[1] = 'b' 然后，由于 position 不再位于 state 列表的末尾，它调用自己再次...现在 position == 2 并且 for 循环设置 state[2] == 'a', 'b', 'c'，依此类推。

顺便说一句，如果你想在 python 中计算笛卡尔积，这里有一个很好的方法，不需要你的读者解析出递归算法:

>>> import itertools
>>> [''.join(c) for c in itertools.product('abc', 'abc', 'abc')]
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 
 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 
 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

你也可以这样做

>>> [''.join(c) for c in itertools.product(*['abc'] * 3)]