python中的排列：超過最大遞歸深度

我正在嘗試使用自適應C++改編的代碼生成置換數字。 Python版本錯誤與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

來源

2015-06-15 zxwjames

您的解決方案不適用於輸入'[1，2，3]'。 – Blender

你的遞歸實際上是加入元素通過線

tempresult[j].insert(0,fixvalue)

您需要更改線路列表

temp = nums

到

temp = nums[:]

這將創建輸入using copy-by-slice的副本。你現在的代碼是操縱原文。

Unrelatedly，我不知道在所有的，爲什麼你有一個Java去年秋季類Solution含permute沒有任何一個國家。爲什麼不簡單地使用permute作爲函數？班級增加了什麼？

來源

2015-06-15 23:30:36

謝謝，你是對的。改變了這條線之後，該程序起作用了！ – zxwjames

您的代碼的邏輯有關於它的列表操作的幾個錯誤。實際上，我對你遇到的錯誤感到有點驚訝，因爲我認爲IndexError會更有可能，但事實證明，你可以像刪除它們一樣往列表中添加新值。

這裏是錯誤的核心：

temp = nums

這並不是我們希望的，如果你從C或C++來。它不復制存儲在nums變量中的列表並將複製的數據存儲爲temp。它只是創建一個對同一個列表對象的引用。當您稍後修改temp（使用del，並且在一些令人困惑的角落案例中，使用insert時），您也正在修改nums。

您應該將Python中的賦值看作類似於C中的指針賦值。兩個指針可以指向內存中的同一個點，並且通過其中一個修改內存將影響您通過其他指針。

至於如何解決這個問題，如果你以某種方式複製你的nums列表的內容，你可能會有更好的運氣。在使用del修改副本之前，您可以使用list或片段nums[:]來複制整個事物，也可以使用兩個較小的片段直接獲取所需值（nums[:i] + nums[i+1:]）。

來源

2015-06-15 23:37:25 Blckknght

如果您只需要排列，python提供了一個現成的解決方案itertools.permutations。

如果你想這樣做，作爲一個練習，有幾個問題與您的代碼：

你必須遞歸之前，在列表的副本
你的遞歸算法需要一個特殊的案例空列表或帶有一個項目的列表，否則它不會退出，因此超出了遞歸限制。

如果你改正你的算法，它仍然超過了遞歸限制，您可以更改遞歸限制（默認1000）有：

sys.setrecursionlimit(10000)

我的建議是看看的official implementation在itertools。

來源

2015-06-16 03:44:42 NeoWang

python中的排列：超過最大遞歸深度

回答

相關問題