python - 这个递归函数如何产生所有排列？

Question

我真的很难理解递归代码。我复制了一段我试图理解的代码。我已经看到以图形方式描述了这一点，但我不明白程序如何得到结果。

这是我目前的理解

最初

• (ABC, 0, 3) 被传递到函数中
• 如果条件不满足，则进入 ELSE分支
• j 是 0 并且这次 i 是 0 （将第一个字符与第一个字符交换）
• **THEN* 将新的“数据”发送回函数并重新运行
• 为什么“j”会随着 i 递增？for 循环还没有运行到完成无论如何....由于某种原因 j 和 i 都增加直到 i = 3 然后打印“ABC”
• 到目前为止，我们还没有超出行 permute(data, i+1, length)
• 我不明白为什么程序在打印“ABC”行后跳转到 permute(data...) 行，我们在“if-else”子句的“IF”而不是“ELSE”分支中。
• 然后我不明白我们如何使用“i”和“j”在所有字符之间迭代。

这有意义吗？请有人能解释一下这段代码是如何产生所有解决方案的。谢谢

def permute(data, i, length): 
    if i==length: 
        print(''.join(data) )
    else: 
        for j in range(i,length): 
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  


string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)

标签： pythonrecursion

Answer 1

让我们逐行分解代码。我们将从字符串的开头一步步到结尾，i在每次调用时递增。在每次调用中，我们迭代j字符串的其余部分。

def permute(data, i, length): 
    # If "i" is at the end, we're done with one permutation: print the result.
    if i==length: 
        print(''.join(data) )

    else:
        # for each remaining character (later in the string)
        for j in range(i,length):

            # Swap that character with the "ith" character
            data[i], data[j] = data[j], data[i]

            # Keeping data[0:i] fixed,
            # generate all permutations of the remainder of the string
            permute(data, i+1, length)

            # Swap the characters back
            data[i], data[j] = data[j], data[i]

现在，添加一些基本的工具来跟踪执行：跟踪例程入口和递归；每次重复时缩进。

indent = ""

def permute(data, i, length): 
    global indent
    print(indent, "ENTER", ''.join(data), i)
    indent += "  "

    if i==length: 
        print("PERMUATATION:", ''.join(data) )
    else: 
        for j in range(i,length): 
            print(indent, "SWAP", i, j)
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  

    indent = indent[2:]


string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)

输出：

 ENTER ABC 0
   SWAP 0 0
   ENTER ABC 1
     SWAP 1 1
     ENTER ABC 2
       SWAP 2 2
       ENTER ABC 3
PERMUATATION: ABC
     SWAP 1 2
     ENTER ACB 2
       SWAP 2 2
       ENTER ACB 3
PERMUATATION: ACB
   SWAP 0 1
   ENTER BAC 1
     SWAP 1 1
     ENTER BAC 2
       SWAP 2 2
       ENTER BAC 3
PERMUATATION: BAC
     SWAP 1 2
     ENTER BCA 2
       SWAP 2 2
       ENTER BCA 3
PERMUATATION: BCA
   SWAP 0 2
   ENTER CBA 1
     SWAP 1 1
     ENTER CBA 2
       SWAP 2 2
       ENTER CBA 3
PERMUATATION: CBA
     SWAP 1 2
     ENTER CAB 2
       SWAP 2 2
       ENTER CAB 3
PERMUATATION: CAB

现在使用此信息跟踪代码。