我有一个这样的矩阵:
http://i.imgur.com/3HiEBm4.png
你可以这样加载它:
matrix = structure(c("-", "-", "C", "G", "C", "A", "-", "0", "V", "V",
"V", "V", "C", "H", "D", "V", "DV", "V", "A", "H", "H", "D",
"DV", "D", "C", "H", "DH", "DH", "D", "V", "G", "H", "H", "D",
"H", "D", "T", "H", "H", "H", "DH", "DH", "A", "H", "H", "H",
"DH", "D", "T", "H", "H", "H", "DH", "H"), .Dim = c(6L, 9L))
从右下角开始,目标是遵循方向(D = 沿对角线向 0 移动,H = 向左移动,V = 向上方移动),以便所有路径都到达零。如您所见,有些单元格具有多个方向(例如 DH)。
我试图通过这样的矩阵找到所有可能的路径。我用递归做到了。但是我很难正确存储路径。似乎当函数返回到旧单元格以转向另一个方向时,它会将路径附加到错误的列表。
这是我的递归函数代码:
threading = function(matrix,i,j,list) { #Function wants the matrix to be threaded, number of rows and cols, and an empty list
if (matrix[i,j] == 0) { #If the recursion has arrived at zero, stop and print out the path that arrived there
print(list)
}
else { #If still elsewhere inside the matrix...
for (move in strsplit(matrix[i,j],"")[[1]]) { #Iterate through each move in that cell
if (move == "D") { #If a move is D...
list = paste(list, "D", sep="") #Append that to the path
threading(matrix,i-1,j-1,list) #Send the function to the diagonal cell
}
if (move == "V") { #If a move is V...
list = paste(list, "V", sep="") #Append that to the path
threading(matrix,i-1,j,list) #Send the function to the above cell
}
if (move == "H") { #If a move is H...
list = paste(list, "H", sep="") #Append that to the path
threading(matrix,i,j-1,list) #Send the function to the left cell
}
}
}
}
所以当我用上面的矩阵运行它时,它给出了这个作为输出:
> threading(matrix, 6,9, emptylist)
[1] "HDDDDHH"
[1] "HDDDDHHD"
[1] "HDDHHDDD"
关键是后两条路径的第二个字符是错误的,但其他一切都是正确的。我该如何避免这种情况?如果不返回旧路径,我无法弄清楚如何正确存储路径。我认为这与追加的顺序和将函数发送到下一个单元格有关,但如果我反转它们,那么追加永远不会发生......
请您参考如下方法:
问题在于:
list = paste(list, "*", sep="")
当您点击一个有两个选择的单元格时,例如“VH”,for
循环将经历两次迭代:list
由第一次迭代修改,然后将修改后的值传递给第二次迭代。相反,每次迭代都必须使用原始值。所以你可以替换为:
l = paste(list, "*", sep="")
并将 l
而不是 list
传递给 threading
调用。
另外,最好避免将变量命名为 matrix
或 list
,因为它们也是函数的名称。