递归只生成一对。我究竟做错了什么？

Question

我正在尝试根据输入列表创建排列。我的递归失败了，只带回了一个应该有多个列表的列表。我不确定我的逻辑有什么问题 - 递归的新手。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer, perm = [], []
        self.dfs(nums, answer, perm)
        return answer

    def dfs(self, nums, answer, perm):
        if not nums:
            answer.append(perm)

        for ind, ele in enumerate(nums):
            perm.append(ele)
            nums.pop(ind)
            self.dfs(nums,answer, perm)

预期：[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3 ,2,1]] 实际：[[1,2,3]]

Answer 1

您的代码的问题是它在 for 循环的每次迭代中从 nums 中删除一个元素，并且 returns 一旦 nums 的答案是清空。因此对于输入 [1,2,3]，首先将 1 附加到 perm 从 nums 中删除，然后 2，然后 3，一旦 num 为空，perm = [1,2,3] 将附加到 ans 并返回。

请注意，您可以简单地使用 itertools 中的 permutations() 方法从列表生成排列：

import itertools

input_list = [1,2,3]
permutations = list(itertools.permutations(input_list))
print(permutations)

输出：

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Answer 2

鉴于您的代码遵循编码挑战中代码问题的格式，我假设您想知道为什么您的解决方案不起作用，而不是使用 python 内置功能的不同解决方案。

作为参考，您可以分两行执行此操作：

import itertools
result = list(itertools.permutations([1, 2, 3]))
print(result)

工作时的问题 lists 是它们都通过指针传递。这是一个递归解决方案。我添加了一些印刷品以便更容易看到发生了什么。

class Solution:
    def permutation(self, s):
        # if our list is only one element
        # then nest our list and return it
        if len(s) == 1:
            return [s]

        perm_list = [] # resulting list
        for element in s:
            # Grab elements other then the one we currently have
            remaining_elements = [x for x in s if x != element]

            # Permute on the remain elements
            # a list is returned
            print("Calling with", remaining_elements)
            permutations = self.permutation(remaining_elements) # permutations of sublist

            for perm in permutations:
                # combine our current element with the permuation
                perm_list.append([element] + perm) 
        print("Returning ", perm_list)
        return perm_list

Answer 3

注销一些通过您的解决方案的数据会很有帮助，这样您就可以准确地看到您做错了什么。如果我们在代码的每一步记录 nums 和 perm，我们会得到以下信息：

[1, 2, 3]             # nums 0
[]                    # perm 0
[2, 3]                # nums 1
[1]                   # perm 1
[3]                   # nums 2
[1, 2]                # perm 2
[]                    # nums 3
[[1, 2, 3]]           # result

您当前的所有代码都将元素从列表移动到包含原始列表的子列表。您需要跟踪哪些元素已添加到子列表而不清空原始列表，然后您可以创建所需的排列。您仍然可以通过递归来完成此操作，但添加 set 的功能将使您的生活更轻松。

这是一个基本示例，您可以根据需要进行调整：

def dfs(data, perm_out=None):
    if not perm_out:
        perm_out = []
    if not data:
        return [perm_out]
    res = []
    for point in data:
        u = {point}
        diff = data - u
        res += dfs(diff, perm_out + [point])
    return res

在您的简单输入数据上调用它：

i = [1, 2, 3]
u = dfs(set(i))
print(u)

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

递归只生成一对。我究竟做错了什么？

Recursion only generating one pair. What am I doing wrong?

python

recursion

backtracking

python-3.x