Trace through the direction matrix in R
I have a matrix like this:
http://i.imgur.com/3HiEBm4.png
You can download it like this:
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))
Starting at the bottom right corner, the goal is to follow the directions (D = move diagonally to 0, H = move left, V = move to above) so that all paths reach zero. As you can see, there are multiple multi-directional cells (like DH).
I'm trying to find ALL possible paths through a matrix like this. I did it with recursion. But I have a hard time keeping the path (s). It seems that when the function goes back to the old cell to go in the other direction, it adds 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 a result:
> threading(matrix, 6,9, emptylist)
[1] "HDDDDHH"
[1] "HDDDDHHD"
[1] "HDDHHDDD"
The kicker is that the second character of the second two paths is wrong, but everything else is correct. How to avoid this? I can't figure out how to save the path correctly without going back to the old path. I think it has to do with the ordering of adding and sending the function to the next cell, but if I cancel them then the addition never happens ...
source to share
The problem is this:
list = paste(list, "*", sep="")
When you click on a cell with two choices, for example. "VH", the loop for
will go through two iterations: it is list
changed by the first iteration, then this modified value is passed to the second iteration. Instead, each iteration must use the original value. Therefore, you can replace with:
l = paste(list, "*", sep="")
and pass l
instead list
to the call threading
.
On a separate note, it is recommended that you avoid naming your variables matrix
or list
because they are also the name of functions.
source to share