python - 在递归函数中附加到列表的干净方法

Question

在为这样的列表查找排列时：

def permut(nums: List[int]) -> List[List[int]]:
    result = []

    def perm(a, k=0):
        if k == len(a):
            result.append(a)
        else:
            for i in range(k, len(a)):
                a[k], a[i] = a[i], a[k]
                perm(a, k + 1)
                a[k], a[i] = a[i], a[k]

    perm(nums)
    return result

这不起作用，因为我a每次都在覆盖，结果只是所有指向的项目列表a

我可以将该行更改为：

result.append([item for item in a])

但这似乎只是一种从 a 创建新列表的技巧。在递归函数中处理追加到列表的更好方法是什么？

标签： python

Answer 1

更好的递归方法是避免自己管理项目来回交换，而是依靠调用堆栈为您执行此操作：

def perm(lst):
    if lst:
        for index, item in enumerate(lst):
            for p in perm(lst[:index] + lst[index + 1:]):
                yield [item, *p]
    else:
        yield []

以便：

for p in perm([1, 2, 3]):
    print(p)

输出：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]