在Python2.7中，如何将这个递归函数（返回3X3矩阵的路径列表）更改为迭代函数？

Question

下面的递归函数有助于找到3X3矩阵的所有路径，从左上到右下，向下或向右移动。但是我想把它变成一个迭代函数，这样我就可以编辑这个函数，只找到一个特定的完整路径（只有1，从左上到右下，通过向右或向下移动），它将（每个点上的值的总和等于一个设定的数）相加到一个所需的数，例如12。这对于更大的矩阵尤其重要，例如9 X 1000矩阵。我该怎么做？你知道吗

Danoran注意事项：
数值总是正的。如果你看我的3X3矩阵a，你会看到1s，2s和3s的值，例如，从1到1到1到2到3（目标）是一个完整的路径，总和是8。你知道吗

这只会找到所有路径

a = []
for i in range(3):
    r = []
    for j in range(3):
        r.append(i+1)
    a.append(r)

a=矩阵

1 1 1

2 2 2

三三三

all_paths = []

def printall(currentRow, currentColumn, nums):
    if (currentRow == len(a) - 1):
        for i in range(currentColumn, len(a[0])):
            nums.append(a[currentRow][i])
        all_paths.append(nums)
        return all_paths

    if (currentColumn == len(a[0]) - 1):
        for i in range(currentRow, len(a)):
            nums.append(a[i][currentColumn])
        all_paths.append(nums)
        return all_paths

    nums.append(a[currentRow][currentColumn])
    printall(currentRow+1, currentColumn, nums[:])
    printall(currentRow, currentColumn+1, nums[:])

printall(0,0,[])

print all_paths

Answer 1

如果有R行和C列，则必须进行R-1跳转和 C-1右跳。这是不变的。唯一的变化是 跳跃。如果我们说dj=R-1和rj=C-1，那么路径的总数 是（dj+rj）！/（主持人！rj！）。你知道吗

所以，我们可以简单地遍历所有唯一的排列。请注意 itertools.permutations()将生成所有置换，而不仅仅是 唯一的，所以我们必须过滤掉重复。当然，这个 也意味着运行时间将与（dj+rj）成正比！，数量 非唯一排列。我不会讨论如何有效地生成 唯一排列；例如参见Question 22431637。你知道吗

在下面的代码中，我将行数增加到了4行，以提供帮助 区分行和列。你知道吗

from itertools import permutations

a = []
for i in range(4):
    r = []
    for j in range(3):
        r.append(i+1)
    a.append(r)

#print a   # Uncomment to trace execution

all_paths = []

def gen_all_paths(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    dj = rows - 1   # down-jumps
    rj = cols - 1   # right-jumps
    pathmix = 'd' * dj + 'r' * rj

    prev = ()
    for path in permutations(pathmix):
        if path <= prev:   # filter out repeats
            continue
        prev = path

        r, c = 0, 0
        cells = [matrix[0][0]]
        for i in path:
            if i == 'd':
                r += 1
            else:
                c += 1
            cells.append(matrix[r][c])
        #print ''.join(path), cells   # Uncomment to trace execution
        all_paths.append(cells)

gen_all_paths(a)

print all_paths