Реализация алгоритма кучи для перестановок в Python

Question

Я пытаюсь реализовать алгоритм Heap в python, но у меня возникают проблемы с повторением некоторых решений. Я озадачен тем, где ошибка. Вот реализация:

import copy

def _permute(l, n):
    if n == 1:
        print(l)
    else:
        for i in range(n - 1):
            # note: must copy here, or all answers will be same
            new_arr = copy.copy(l)
            _permute(new_arr, n - 1)

            if n % 2 == 0:
                l[i], l[n - 1] = l[n - 1], l[i]
            else:
                l[0], l[n - 1] = l[n - 1], l[0]

        _permute(l, n - 1)

Для ввода [0, 1, 2] и 3 я получаю:

[0, 1, 2]
[1, 0, 2]
[2, 1, 0]
[1, 2, 0]
[0, 1, 2] ** repeats from first answer **
[1, 0, 2] ** repeats from second answer **

С двумя последними результатами, повторяющимися с первого и второго, пропущенными :

[0, 2, 1]
[2, 0, 1]

Я искал несколько мест и пробовал разные реализации этого алгоритма, но независимо от того, сколько раз я пытался, я не могу заставить его работать. Чего мне не хватает?

Answer 1

Вы делали рекурсивный вызов не в том месте, это должно помочь (и вы не должны использовать копию):

def _permute(l, n):
    if n == 1:
        print(l)
    else:
        _permute(l, n - 1)
        for i in range(n - 1):
            if n % 2 == 0:
                l[i], l[n - 1] = l[n - 1], l[i]
            else:
                l[0], l[n - 1] = l[n - 1], l[0]

            _permute(l, n - 1)