Python字符串置換超出遞歸限制

Question

我寫了一個Python程序給一個字符串的所有排列，使用回溯：

class Solution(object): 
    def permute(self, nums): 
     """ 
     :type nums: List[int] 
     :rtype: List[List[int]] 
     """ 
     if nums == None or len(nums) <= 1: 
      return [nums] 

     res_lst = [] 
     res = [] 
     self.permuteHelper(res_lst, nums, res) 
     return res_lst 

    def permuteHelper(self, res_lst, nums, res): 
     if len(res) == len(nums): 
      res_lst.append(res) 
      return 

     for n in nums: 
      if n not in res: 
       self.permuteHelper(res_lst, nums,res+[n]) 
       res = res[:-1] #Prune back one node 

這一個總是超過最大遞歸限制。因爲在每個遞歸步驟中，我將結果列表+ [n]傳遞給下一個遞歸調用，我想它最終會達到len（res）== len（nums）。

Doe有人知道爲什麼不會發生？

Answer 1

啊，那很微妙。刪除線：

res = res[:-1] #Prune back one node 

它的工作原理。你從給定的排列中移除一個數字，這意味着每次你這樣做時，你遞歸遞歸遞增一個遞歸級別，所以你不得不越來越深。

此外，它完全混淆了排列。

Answer 2

下面是一個迭代實現置換：

import itertools 

def permutations(*args): 
    res = list(args) 
    if len(res) > 0: 
    for n in itertools.count(): 
     yield tuple(res) 
     i = x = 2 
     while n % x == x - 1: 
     i += 1 
     x *= i 
     if i > len(res): 
     break 
     j = (n + 1) % x * i // x 
     res[-i], res[-j] = res[-j], res[-i] 
     res[1 - i:] = res[:-i:-1] 

注意，這不具有重複值的任何特殊處理。