python - 矩阵的自定义回溯功能不起作用

Question

我正在尝试在 Python 3 中实现用于 RNA 折叠的 Nussinov 算法。

到目前为止，我已经有了正确的矩阵，我正在尝试通过这个矩阵traceback。

本质上，该函数应从矩阵的右上角单元格开始，并根据算法继续遍历单元格，直到到达对角线。

问题是 structure 列表没有变化。谁能告诉我为什么？

structure = list()

for base in seq:
    structure.append('.')

def traceback(i, j, matrix1):
    if j - i > 0:
       return

    elif matrix1[i][j] == matrix1[i+1][j]: # if value same as cell under i,j
        traceback(i+1, j, matrix1)

    elif matrix1[i][j] == matrix1[i][j-1]: # if value same as cell on left of i,j
        traceback(i, j-1, matrix1)

    elif matrix1[i][j] == (matrix1[i+1][j-1] + 1):
        traceback(i+1, j-1, matrix1)
        structure[i] = '('
        structure[j] = ')'

print(matrix1)
traceback(0, n-1, matrix1)

Answer 1

你的矩阵永远不会发生任何事情，因为你的第一个 if-check 总是会提前返回:

def traceback(i, j, matrix1):
    if j - i > 0:
        return
    ...

traceback(0, n-1, matrix1)

为了超越第一次回归，j应小于 i ， 正确的？现在观察您的输入:

   (n - 1) - 0 <= 0
=> n - 1 <= 0
=> n <= 1

所以在当前状态下，您的 traceback当且仅当 n == 0 时函数将执行矩阵元素检查或 n == 1 ，都是空子矩阵或标量子矩阵的平凡情况。

我想第一个 block 应该将遍历限制在主对角线上方的上三角形？然后简单地翻转标志:

if j - i < 0:
    return