递归只产生了一对。我做错了什么？

Question

递归只产生了一对。我做错了什么？

3

我试图从输入列表中创建排列。我的递归失败了，只返回一个列表，而不是多个列表。我不确定我的逻辑有什么问题——对递归不熟悉。

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

- rkowalk

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- glhr · Answer 1

你的代码问题在于每次迭代 for 循环时都会从 nums 中删除一个元素，并在 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)]

- Error - Syntactical Remorse · Answer 2

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

参考资料，您可以用两行代码完成此操作：

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

在处理列表时的问题在于它们都通过指针传递。这里提供了一种递归解决方案。我添加了一些打印语句，以便更容易地查看发生了什么。

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

- user3483203 · 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]]