通过R中的方向矩阵进行回溯 [英] Traceback through a Matrix of Directions in R

问题描述

我有一个像这样的矩阵:

I have a matrix like this:

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).

Starting at the bottom-right corner, the goal is to follow the directions (D = move diagonally towards 0, H = move to the left, V = move to the above) so that all paths arrive at zero. As you can see, there are some cells with multiple directions (such as DH).

我正在尝试通过这种矩阵找到所有可能的路径.我做到了递归.但是我在正确存储路径方面遇到困难.似乎当函数返回到旧单元格以朝另一个方向移动时，它将路径追加到错误的列表中.

I'm trying to find ALL possible paths through such a matrix. I did it with recursion. But I'm having difficulty with storing the path(s) properly. It seems like when the function returns to an old cell to take the other direction, it appends the path to the wrong list.

这是我的递归函数代码:

Here's my code for the recursive function:

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
      }
    }
  }
}

因此，当我使用上述矩阵运行它时，它将作为输出:

So when I run it with the above matrix, it gives this as an output:

> threading(matrix, 6,9, emptylist)
[1] "HDDDDHH"
[1] "HDDDDHHD"
[1] "HDDHHDDD"

更重要的是，后两条路径的第二个字符是错误的，但其他所有内容都是正确的.我该如何避免呢?我无法弄清楚如何正确存储路径，而又不能回到旧路径.我认为这与追加的顺序以及将函数发送到下一个单元格有关，但是如果我反转它们，则追加永远不会发生...

The kicker is that the second character of the second two paths are wrong but everything else is right. How do I avoid that? I can't figure out how to store the path properly without it going back to an old path. I think it's something to do with the ordering of the appending and the sending the function to the next cell but if I reverse them then the appending never happens...

推荐答案

问题出在:

list = paste(list, "*", sep="")

当您击中具有两个选择的单元格时，例如"VH"，for循环将经历两次迭代:list由第一次迭代修改，然后将该修改后的值传递给第二次迭代.相反，每次迭代都必须使用原始值.因此，您可以替换为:

When you hit a cell with two choices, e.g. "VH", the for loop will go through two iterations: list is modified by the first iteration, then that modified value is passed to the second iteration. Instead, each iteration must use the original value. So you could replace with:

l = paste(list, "*", sep="")

并将l而不是list传递给threading调用.

and pass l instead of list to the threading call.

另外，最好避免命名变量matrix或list，因为它们也是函数的名称.

On a separate note, it is good practice to avoid naming your variables matrix or list because they are also the name of functions.

这篇关于通过R中的方向矩阵进行回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！