通过递归排列数组，何时进行第二个元素交换？

Question

这个排列程序中的第二个元素交换是如何工作的？第二次交换发生在程序的哪一步？在第一次递归之后还是在所有递归完成之后？

def permutations(A: List[int]) -> List[List[int]]:
    def directed_permutations(i):
        if i == len(A) - 1:
            result.append(A.copy())
            return  

        # Try every possibility for A[i]
        for j in range(i, len(A)):
            A[i], A[j] = A[j], A[i]
            # Generate all permutations for A[i + 1:]
            directed_permutations(i + 1)
            # Second element swap, which I do not understand
            A[i], A[j] = A[j], A[i]

    result: List[List[int]] = []
    directed_permutations(0)
    return result

当我离开第二个交换并尝试 A = [2,3,5,7] 我得到 4！元素，但有重复：

[[2, 3, 5, 7], [2, 3, 7, 5], [2, 7, 3, 5], [2, 7, 5, 3], [2, 3 , 5, 7], [2, 3, 7, 5], [3, 2, 7, 5], [3, 2, 5, 7], [3, 5, 2, 7], [3, 5 , 7, 2], [3, 2, 7, 5], [3, 2, 5, 7], [5, 2, 3, 7], [5, 2, 7, 3], [5, 7 , 2, 3], [5, 7, 3, 2], [5, 2, 3, 7], [5, 2, 7, 3], [3, 2, 7, 5], [3, 2 , 5, 7], [3, 5, 2, 7], [3, 5, 7, 2], [3, 2, 7, 5], [3, 2, 5, 7]]

通过第二次交换，我得到了正确的 4！元素：

[[2, 3, 5, 7], [2, 3, 7, 5], [2, 5, 3, 7], [2, 5, 7, 3], [2, 7 , 5, 3], [2, 7, 3, 5], [3, 2, 5, 7], [3, 2, 7, 5], [3, 5, 2, 7], [3, 5 , 7, 2], [3, 7, 5, 2], [3, 7, 2, 5], [5, 3, 2, 7], [5, 3, 7, 2], [5, 2 , 3, 7], [5, 2, 7, 3], [5, 7, 2, 3], [5, 7, 3, 2], [7, 3, 5, 2], [7, 3 , 2, 5], [7, 5, 3, 2], [7, 5, 2, 3], [7, 2, 5, 3], [7, 2, 3, 5]]

Answer 1

递归的规则是（几乎总是）你不要让子问题中的状态改变改变父状态。每个调用框架不应该知道或关心（可能遥远的）子调用中发生的事情，从而保留递归自相似性。参数数据结构应该是有效的不可变的。

post-递归调用交换通过执行调用前交换的撤消来实现不变性，return将列表恢复到循环迭代之前的状态。这种状态恢复对于正确性至关重要，因为没有它，循环的下一次迭代（以及之后的每一次迭代）将有一个列表，该列表已被先前迭代中的任意嵌套子调用修改，从而破坏了每个循环的有条不紊的枚举方法递归调用框架交换 i 处的元素与每个元素 j，然后递归从 i + 1 开始的列表的其余部分，并为剩余的子调用固定 0..i .

为了表明不可变性是关键因素，而撤消交换只是实现这一点的一种手段，您可以编写算法，在将参数列表作为参数传递时复制参数列表：

from typing import List

def permutations(A: List[int]) -> List[List[int]]:
    result = []

    def directed_permutations(A, i=0):
        if i == len(A) - 1:
            result.append(A)
        else:
            for j in range(i, len(A)):
                B = A[:]
                B[i], B[j] = B[j], B[i]
                directed_permutations(B, i + 1)

    directed_permutations(A)
    return result

if __name__ == "__main__":
    print(permutations([1, 2, 3]))

请注意，我们不再需要在附加到结果时进行复制，因为现在每个帧都有一个唯一的列表可以进行操作，而无需担心混叠。不过，与原始方法相比，这种方法会产生更多的复制开销。

这不是重点，但我会 return 像这样的算法的生成器，就像 itertools 那样。

通过递归排列数组，何时进行第二个元素交换？

Permutation of an array by recursion, when does the second element swap take place?

python

algorithm

recursion

permutation