python - 列表變量不存儲適當的結果在遞歸

Question

我想通過遞歸存儲列表的所有可能的括號。

例子：printRange(0,3) 答案是[[0],[1], [2]], [[0], [1, 2]], [[0, 1], [2]], [[0, 1, 2]]

我能得到一個正確的答案，當我試圖打印在側的功能。當我嘗試存儲結果，並打印出來後，我沒有得到期望的結果。

的代碼如下：

res=[] 
def printRange(st,size,cans=[]): 


    if(st==size): 
     res.append([]+cans) 
     print cans 

    l=[] 

    for i in range(st,size): 
     l.append(i) 
     tmp=[]+cans 
     tmp.append(l) 
     printRange(i+1,size,[]+tmp) 

printRange(0,3) 
print res 

當我運行上面的代碼我得到：

[[0], [1], [2]] 

[[0], [1, 2]] 

[[0, 1], [2]] 

[[0, 1, 2]] 

[[[0, 1, 2], [1, 2], [2]], [[0, 1, 2], [1, 2]], [[0, 1, 2], [2]], [[0, 1, 2]]] 

爲什麼RES變量未存儲該預期的結果？

Answer 1

發生這種情況的原因是cans是一個列表列表，這些內部列表發生了變異。您需要將cans的深層副本附加到res，即複製內部列表的副本。你可以使用deepcopy從copy模塊來做到這一點，或者只是寫一個適用於列表清單的簡單深層拷貝。

下面是您的代碼的修復版本。

#from copy import deepcopy 

def deepcopy(list2d): 
    return [u[:] for u in list2d] 

res = [] 
def printRange(st, size, cans=[]): 
    if(st == size): 
     res.append(deepcopy(cans)) 
     print cans 

    l = [] 
    for i in range(st, size): 
     l.append(i) 
     tmp = [] + cans 
     tmp.append(l) 
     printRange(i+1, size, tmp) 

printRange(0, 4) 
print res 

輸出

[[0], [1], [2], [3]] 
[[0], [1], [2, 3]] 
[[0], [1, 2], [3]] 
[[0], [1, 2, 3]] 
[[0, 1], [2], [3]] 
[[0, 1], [2, 3]] 
[[0, 1, 2], [3]] 
[[0, 1, 2, 3]] 
[[[0], [1], [2], [3]], [[0], [1], [2, 3]], [[0], [1, 2], [3]], [[0], [1, 2, 3]], [[0, 1], [2], [3]], [[0, 1], [2, 3]], [[0, 1, 2], [3]], [[0, 1, 2, 3]]] 

---

需要注意的是，一般不是一個好主意，用一個列表或其他可變對象作爲默認參數，因爲默認參數分配時的功能被定義，而不是被調用時，這可能會導致令人驚訝的行爲。它實際上並沒有給你的代碼帶來問題，但是避免默認的可變參數仍然是一個好主意，除非你需要這種「有趣的」行爲，例如它可以用作memoization緩存，即使這樣你也應該使用註釋解釋說你是故意這樣做的。 :)有關更多詳細信息，請參見「Least Astonishment」 and the Mutable Default Argument。

---

我會用稍微不同的方式來處理這個任務，用我最喜歡的「玩具」之一：遞歸 generator。

def brackets(n): 
    if n == 0: 
     yield [[0]] 
    else: 
     for seq in brackets(n - 1): 
      yield seq + [[n]] 
      yield seq[:-1] + [seq[-1] + [n]] 

for seq in brackets(3): 
    print seq 

輸出

[[0], [1], [2], [3]] 
[[0], [1], [2, 3]] 
[[0], [1, 2], [3]] 
[[0], [1, 2, 3]] 
[[0, 1], [2], [3]] 
[[0, 1], [2, 3]] 
[[0, 1, 2], [3]] 
[[0, 1, 2, 3]] 

如果你真的想包含所有結果的列表，只是通過發電機到list構造：

res = list(brackets(2)) 
print res 

輸出

[[[0], [1], [2]], [[0], [1, 2]], [[0, 1], [2]], [[0, 1, 2]]]