上列出

Question

的列表遞歸發生器我有2個降級名單看起來像：

[[1,2,3,], 
[4,5,6], 
[7,8,9]] 

我想寫一個發生器，產生「路徑」的總和。

「路徑」從左上角開始，只在x + 1和y + 1上，直到到達最後一個元素（右下角）。

例如，有效路徑是1=>2=>5=>6=>9 (sum=23)。

無-有效的路徑可能是1=>2=>5=>**4**=> ...

到目前爲止，我有這樣的代碼：

my_list = [[0, 2, 5], [1, 1, 3], [2, 1, 1]] 
def gen(x, y, _sum): 
    if x + 1 <= len(my_list): 
     for i1 in gen(x + 1, y, _sum + my_list[y][x]): 
      yield _sum 
    if y + 1 <= len(my_list): 
     for i2 in gen(x, y + 1, _sum + my_list[y][x]): 
      yield _sum 
    yield _sum + my_list[y][x] 


g = gen(0, 0, 0) 
total = 0 
for elm in g: 
    total += elm 

print total 

我得到的錯誤：

for i2 in gen(x, y+1, _sum+my_list[y][x]): 
IndexError: list index out of range 

Answer 1

這樣做的原因是錯誤一個簡單的錯過的錯誤。*

我想你在這裏想要的是x <= len(my_list)或等同於x+1 < len(my_list);你已經將+ 1-ness加倍，導致你跑到列表的最後。

考慮一個具體的例子：

• len(my_list)爲3 x是2。所以，x+1 <= len(my_list)是3 <= 3，這是真的。所以你用gen(3, …)遞歸地調用自己。
• 在這種遞歸調用，4 <= 3是假的，所以，這取決於y值，你可以調用之一：
  • gen(x, y + 1, _sum + my_list[y][3])，或
  • _sum + my_list[y][3]
  • ......其中任何一個都會引發IndexError。

顯然，你需要與y解決同樣的問題與x。

你可以看到它運行沒有錯誤here。

---

當然，實際上並沒有打印出正確的結果，因爲代碼中還存在其他問題。關閉我的頭頂：

• total = + elm內容替換total無論是與elm值。你可能想要+=，而不是= +在這裏。
• 一遍又一遍地產生_sum並且忽略遞歸生成器產生的值不可能有任何好處。也許你想產生i1和i2而不是？

我不能保證這些是你的代碼中唯一的問題，只是他們是問題。

---

_{*我在此假設這是一個愚蠢的錯誤，而不是一個根本性的錯誤，你清楚的知道，索引是從0開始，因爲你gen(0, 0, 0)而非gen(1, 1, 0)調用的函數。}

Answer 2

如果你真的想通過一個N×M矩陣強制所有允許的路徑，那麼簡單地生成N - 1的所有置換移動到右邊加上M - 1向下移動，然後使用這些移動來求和沿着路徑的值：

from itertools import permutations 

def gen_path_sum(matrix): 
    N, M = len(matrix), len(matrix[0]) 
    for path in permutations([(1, 0)] * (N - 1) + [(0, 1)] * (M - 1)): 
     sum = matrix[0][0] 
     x = y = 0 
     for dx, dy in path: 
      x += dx; y += dy 
      sum += matrix[x][y] 
     yield sum 

這會產生（N + M）！路徑;對於3乘3矩陣有720條這樣的路徑。

但是，如果您試圖通過矩陣找到最大路徑，那麼您就是以低效率的方式來解決這個問題。

您可以改爲計算矩陣中任何單元格的最大路徑;它只是上方和左側單元格的最大路徑值中的最大值，加上當前單元格的值。因此，對於左上方的單元格（沒有上方或右側的單元格），最大路徑值是單元格的值。

可以計算用n×m個循環中的所有這些值：

def max_path_value(matrix): 
    totals = [row[:] for row in matrix] 
    for x, row in enumerate(totals): 
     for y, cell in enumerate(row): 
      totals[x][y] += max(
       totals[x - 1][y] if x else 0, 
       totals[x][y - 1] if y else 0 
      ) 
    return totals[-1][-1] 

這隻需要在總n×m個的步驟，或9點的步驟爲您的3×3矩陣。這比蠻力方法好80倍。

對比度只會隨着矩陣大小的增加而增加;一個10x10矩陣，暴力強制，需要檢查2432902008176640000路徑（== 20！），或者你可以用100步計算最大路徑。