Перестановка в python: превышена максимальная глубина рекурсии

Question

Я пытаюсь создать номера перестановок, используя код, который я адаптировал из C++. Версия Python ошибется с

Line 42: RuntimeError: maximum recursion depth exceeded 

для ввода [5,4,6,2].

class Solution: 
    # @param {integer[]} nums 
    # @return {integer[][]} 
    def permute(self, nums): 
     result = [] 

     if len(nums) == 0: 
      return result 

     if len(nums) == 1: 
      result.append(nums) 
      return result 

     if len(nums) == 2: 
      result.append(nums) 
      a = nums[0] 
      b = nums[1] 
      newrow = [b,a] 
      result.append(newrow) 
      return result 

     for i in range(0, len(nums)): 
      temp = nums 
      fixvalue = temp[i] 
      del(temp[i]) 
      tempresult = self.permute(temp) 

      for j in range(0, len(tempresult)): 
       tempresult[j].insert(0,fixvalue) 
       result.append(tempresult[j]) 

     return result 

Answer 1

Ваш рекурсия на самом деле добавление элементов в списке через линию

tempresult[j].insert(0,fixvalue) 

Вам нужно изменить строку

temp = nums 

в

temp = nums[:] 

Это создаст копию ввода using copy-by-slice. Ваш настоящий код управляет оригиналом.

---

Unrelatedly, я не уверен, что у всех, почему у вас есть Java-эск классаSolution содержащий permute без какого-либо государства вообще. Почему бы просто не использовать permute в качестве функции? Что добавляет класс?

Answer 2

Логика вашего кода содержит несколько ошибок в отношении его манипулирования списками. Я на самом деле немного удивлен ошибкой, которую вы получаете, поскольку я бы подумал, что более вероятным будет IndexError, но, оказывается, вы добавляете новые значения в свои списки так часто, как вы их удаляете.

Вот суть ошибки:

temp = nums 

Это не делать то, что вы ожидаете, если вы пришли из C или C++. Он не копирует список, хранящийся в переменной nums, и сохраняет скопированные данные как temp. Он просто создает ссылку на тот же объект списка. Когда вы позже измените temp (с del, а в некоторых запутанных угловых случаях, с insert), вы также изменяете nums.

Вы должны думать о присвоениях в Python как о назначении указателя в C. Два указателя могут ссылаться на одну и ту же точку в памяти, и изменение этой памяти через один из них повлияет на то, что вы видите, когда читаете память через другой указатель.

Как решить проблему, вам, вероятно, повезет, если вы скопируете содержимое своего списка nums в некотором роде. Вы можете использовать list или ломтик nums[:], чтобы скопировать все это, прежде чем использовать del, чтобы изменить копию, или вы можете использовать два меньших фрагмента, чтобы получить нужные значения напрямую (nums[:i] + nums[i+1:]).

Answer 3

Если вам просто нужны перестановки, python предоставляет готовое решение в itertools.permutations.

Если вы хотите сделать это в качестве упражнения, есть несколько проблем с кодом:

• Вы должны сделать копию списка до того рекурсии
• Ваш алгоритм рекурсии необходим специальный случай для пустой список или список с одним элементом, иначе он не выйдет, поэтому предел рекурсии будет превышен.

Если вы исправить алгоритм, и он все еще превышает предел рекурсии, вы можете изменить предел рекурсии (по умолчанию 1000) с:

sys.setrecursionlimit(10000) 

Мое предложение взглянуть на official implementation в itertools.