为什么这个字符串置换码会超过递归限制呢？

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)。

有人知道为什么没有发生这种情况吗？

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]

请注意，这对重复值没有任何特殊处理。

为什么这个字符串置换码会超过递归限制呢？

Why does this string permutation code exceed the recursion limit?

python

recursion

permutation

backtracking