python - Python递归问题【leetcode问题】

问题描述

以上是问题。它是为给定的整数数组找到所有排列（所有不齐）

实际问题

我正在尝试检查蛮力方法置换方法（不寻找最佳解决方案）。我发现自己陷入了这个特殊的问题。用于存储每次递归调用更改的排列的结果数组。我无法理解它为什么会这样。需要帮助弄清楚。

我已经包含了来自代码不同位置的 print() 用于调试目的。如果您需要任何其他信息来帮助您找到答案，请告诉我。

算法演练

element_map ->在这种情况下为输入数组[False,False,False]的每个位置存储 False temp_result -> 在每个步骤中存储临时排列

permutation 函数遍历输入数组的每个 val 并将排列存储在temp_result数组中。
一旦将元素添加到temp_result，它将element_map 标记为 True 并再次递归调用排列函数。
递归结束是 if len(temp_result) == len(nums)。在这种情况下，我们得到一个排列并将其添加到结果中。
一旦遇到基本情况 3，我们设置element_map[i] = False并从temp_result弹出最后一个 val

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        if len(nums) == 1:
            return [nums]
        
        result = []
        element_map = defaultdict(bool)
        for i in range(len(nums)):
            element_map[i] = False
        
        def permutations(nums, temp_result, element_map):
            nonlocal result
            print("Start result ->", result)
            print("Start temp_result ->", temp_result)
            
            if len(temp_result) == len(nums):
                result.append(temp_result)
                print(len(temp_result),len(nums))
                print("temp_result ->", temp_result)
                print("result-> ",result)
                return
            
            for i,val in enumerate(nums):
                
                if not element_map[i]:
                    element_map[i] = True
                    temp_result.append(val)
                    permutations(nums, temp_result, element_map)
                    temp_result.pop()
                    element_map[i] = False
        
        temp_result = []
        permutations(nums, temp_result, element_map)
        print(result)

输入 [1,2,3] 的代码输出。问题是结果不断变化。

Start result -> []
Start temp_result -> []
Start result -> []
Start temp_result -> [1]
Start result -> []
Start temp_result -> [1, 2]
Start result -> []
Start temp_result -> [1, 2, 3]
3 3
temp_result -> [1, 2, 3]
result->  [[1, 2, 3]]
Start result -> [[1, 3]]
Start temp_result -> [1, 3]
Start result -> [[1, 3, 2]]
Start temp_result -> [1, 3, 2]
3 3
temp_result -> [1, 3, 2]
result->  [[1, 3, 2], [1, 3, 2]]
Start result -> [[2], [2]]
Start temp_result -> [2]
Start result -> [[2, 1], [2, 1]]
Start temp_result -> [2, 1]
Start result -> [[2, 1, 3], [2, 1, 3]]
Start temp_result -> [2, 1, 3]
3 3
temp_result -> [2, 1, 3]
result->  [[2, 1, 3], [2, 1, 3], [2, 1, 3]]
Start result -> [[2, 3], [2, 3], [2, 3]]
Start temp_result -> [2, 3]
Start result -> [[2, 3, 1], [2, 3, 1], [2, 3, 1]]
Start temp_result -> [2, 3, 1]
3 3
temp_result -> [2, 3, 1]
result->  [[2, 3, 1], [2, 3, 1], [2, 3, 1], [2, 3, 1]]
Start result -> [[3], [3], [3], [3]]
Start temp_result -> [3]
Start result -> [[3, 1], [3, 1], [3, 1], [3, 1]]
Start temp_result -> [3, 1]
Start result -> [[3, 1, 2], [3, 1, 2], [3, 1, 2], [3, 1, 2]]
Start temp_result -> [3, 1, 2]
3 3
temp_result -> [3, 1, 2]
result->  [[3, 1, 2], [3, 1, 2], [3, 1, 2], [3, 1, 2], [3, 1, 2]]
Start result -> [[3, 2], [3, 2], [3, 2], [3, 2], [3, 2]]
Start temp_result -> [3, 2]
Start result -> [[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]
Start temp_result -> [3, 2, 1]
3 3
temp_result -> [3, 2, 1]
result->  [[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]
[[],[],[],[],[],[]]

标签： pythonpython-3.xrecursion

我已经写了一个替代你的功能。我已经用 Python2 对此进行了测试，但它也应该适用于 Python3。

Arr = [1, 2, 3, 4, 5]

def permute(arr):
    myresult = []
    for i in range(len(arr)):
        sarr = arr[:i] + arr[i+1:]
        el = arr[i]
        if len(sarr) != 0:
            a = permute(sarr)
            for result in a:
                c = [el] + result
                myresult.append(c)
        else:
            return [[el]]
    return myresult

p = permute(Arr)
print str(p)

myresult将是置换函数的结果。 sarr代表“较小的数组”。 el代表元素（数组的）。

这个想法是选择一个元素并连接剩余数组的每个排列。通过使用递归，将处理整个输入数组

python - Python递归问题【leetcode问题】

问题描述

解决方案

推荐阅读