Почему содержимое массива стирается и возвращается к первому результату для рекурсивной функции?

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

Проблема в строке

output.append(a)

выглядит нормально, но позже список a меняется, и когда вы снова добавляете его к output,предыдущие a (которые вы уже добавили) изменения.

Чтобы решить проблему, вы можете просто использовать мелкую копию. Напишите это вместо:

output.append(a[:])

Answer 2

Знаете ли вы, что в python есть существующая функция?

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')