How to traverse matrix in diagonal strips and return the index of each position?

Question

Have a matrix N x N and I want to traverse this matrix in diagonal strips and return the index position.

If I have a matrix 4x4 the code should return (1,1); (1,2); (2,1); (1,3); (2,2); (3,1); (1,4); (2,3); (3,2); (4,1); and so on

I'm trying to do this in R Studio

Answer 1

1) row(m) + col(m) is constant along reverse diagonals and within reverse diagonal we order by row:

m <- matrix(1:16, 4, 4) # test matrix

m[order(row(m) + col(m), row(m))]
## [1]  1  5  2  9  6  3 13 10  7  4 14 11  8 15 12 16

2) Not quite as compact as (1) but here is a variation that uses the same principle but uses outer and recycling instead of row and col:

k <- nrow(m)
m[ order(outer(1:k, 1:k, "+") + 0:(k-1)/k) ]
## [1]  1  5  2  9  6  3 13 10  7  4 14 11  8 15 12 16

Answer 2

You can use three for loops - the outermost one can count which diagonal you're on. It goes from 1 to N*N - 1 (one diagonal for each X value, one for each Y value, and then one that they share, starting at (1,N) and going to (N,1).

From there you only need to calculate the X and Y values in the inside 2 loops, using the diagonal counter

Answer 3

No loops needed with R's matrix indexing.

One test for whether a row,col number is the same diagonal is row+col being the same. You can also order the row and columns of a matrix by this principle, so use a two column matrix to deliver the values in the order:

 M <- matrix(1:16, 4, 4)
 idxs <- cbind( c(row(M)), c(col(M)) )
 imat <- idxs[ order( rowSums(idxs), idxs[,1] ), ] # returns two columns
              # turns out you don't need to sort by both rows and columns
              # but could have used rev(col(M)) as secondary sort

>  imat
      [,1] [,2]
 [1,]    1    1
 [2,]    1    2
 [3,]    2    1
 [4,]    1    3
 [5,]    2    2
 [6,]    3    1
 [7,]    1    4
 [8,]    2    3
 [9,]    3    2
[10,]    4    1
[11,]    2    4
[12,]    3    3
[13,]    4    2
[14,]    3    4
[15,]    4    3
[16,]    4    4
 M[ imat ]
 #[1]  1  5  2  9  6  3 13 10  7  4 14 11  8 15 12 16