在Python中实现堆的置换算法

Question

我正在尝试在python中实现Heap的算法，但是在重复某些解决方案时遇到了麻烦。我对错误所在的位置感到困惑。这是实现：

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 **

具有最后2个结果，从第一个和第二个重复，缺少：

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

我已经搜索了多个地方并尝试了该算法的不同实现，但是无论我尝试多少次，我似乎都无法使其正常工作。我想念什么？

Answer 1

看看this。尝试使用

if n == 1:
 return n