为什么要擦除数组内容并将其重置为递归函数的第一个结果？

Question

问题源于第三行的output.append（a）。理想情况下，该程序将输出输入字符串的6个唯一排列，但在递归循环中返回第一个结果的6个。我知道退出递归可能与要修改的数组有关，但是如何避免这个问题才能返回解决方案数组？

def permute(a, l, r, output):
    if l==r:
        output.append(a)
    else:
        for i in range(l,r+1):
            a[l], a[i] = a[i], a[l]
            permute(a, l+1, r,output)
            a[l], a[i] = a[i], a[l] # backtrack

用于测试以上功能的驱动程序

string = "ABC"
output = []
n = len(string)
a = list(string)
permute(a, 0, n-1,output)
print(output)

供参考，这是输出的样子：

[['A', 'C', 'B']]
[['B', 'A', 'C'], ['B', 'A', 'C']]
[['B', 'C', 'A'], ['B', 'C', 'A'], ['B', 'C', 'A']]
[['C', 'B', 'A'], ['C', 'B', 'A'], ['C', 'B', 'A'], ['C', 'B', 'A']]
[['C', 'A', 'B'], ['C', 'A', 'B'], ['C', 'A', 'B'], ['C', 'A', 'B'], ['C', 'A', 'B']]
[['A', 'B', 'C'], ['A', 'B', 'C'], ['A', 'B', 'C'], ['A', 'B', 'C'], ['A', 'B', 'C'], ['A', 'B', 'C']]

当输出应为：

['A', 'B', 'C']
['A', 'C', 'B']
['B', 'A', 'C']
['B', 'C', 'A']
['C', 'B', 'A']
['C', 'A', 'B']

Answer 1

您知道python中有一个existing函数吗？

import itertools 

listA = ["A", "B", "C"]
perm = itertools.permutations(listA) 

for i in list(perm): 
    print(i)

结果：

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

Answer 2

问题出在行中

output.append(a)

它看起来不错，但稍后在列表a上进行了更改，并且当您再次将其附加到output时，先前的a（您已经附加的）将发生更改。

要解决该问题，您可以简单地使用浅拷贝。改写这个：

output.append(a[:])