python - 在 python 中使用递归查找列表 int 的排列时考虑索引？

Question

我正在尝试使用递归查找特定范围内整数列表的所有排列。例如，如果 lst = [0,1,2]，则调用 def permute(lst, 0, 1) 应该返回 [[0, 1], [1,0]] 格式。同样，调用 permute(lst, 0, 2) 应该返回 [[0,1,2], [0,2,1]...]。

到目前为止，我的代码只能找到整个列表的排列，从索引 0 到 len(lst):

def permute(lst, low, high):
    if low == high:
        print(lst)
    for index in range(low, high + 1):
            lst[index], lst[low] = lst[low], lst[index]
            permute(lst, low + 1, high)
            lst[index], lst[low] = lst[low], lst[index]

其中 low = 0 和 high 是 len(lst)。

如果我更改这段代码中的索引，我不会得到正确的输出。关于如何考虑指数的任何建议？

Answer 1

您可以使用内部递归函数来执行此操作，例如:

def permute(lst, start, end):
    def permutations(l):
        if len(l) <= 1:
            return [l]
        a = []
        for p in permutations(l[:-1]):
            for i in range(len(l)):
                a.append(p[i:] + [l[-1]] + p[:i])
        return a
    return permutations(lst[start:end+1])

In []
lst = [0,1,2,3,4]
permute(lst, 0, 1)

Out[]:
[[0, 1], [1, 0]]

In []
permute(lst, 0, 2)

Out[]:
[[0, 1, 2], [1, 2, 0], [2, 0, 1], [1, 0, 2], [0, 2, 1], [2, 1, 0]]