Transforming matrix diagonals to ragged array?

Question

I'm trying to come up with a non brute-force solution to the following problem. Given a matrix of arbitrary size:

[6  0  3  5]
[3  7  1  4]
[1  4  8  2]
[0  2  5  9]

Transform its diagonals to a list of vectors, like so:

(0)
(1, 2)
(3, 4, 5)
(6, 7, 8, 9)
(0, 1, 2)
(3, 4)
(5)

(Working from bottom left to top right in this example)

Is there an elegant way to do this short of iterating up the left column and across the top row?

Answer 1

I would just write a little function to transform the vector indices into matrix indices.

Say the matrix is NxN square, then there will be 2N-1 vectors; if we number the vectors from 0 to 2N-2, element k of vector n will be at row max(N-1-n+k,k) and column max(n+k-N+1,k) (or in reverse, the matrix element at row i, column j will be element min(i,j) of vector N-1+j-i). Then whenever you need to access an element of a vector, just convert the coordinates from k,n to i,j (that is, convert vector indices to matrix indices) and access the appropriate element of the matrix. Instead of actually having a list of vectors, you'll wind up with something that emulates a list of vectors, in the sense that it can give you any desired element of any vector in the list - which is really just as good. (Welcome to duck typing ;-)

If you're going to access every element of the matrix, though, it might just be quicker to iterate, rather than doing this computation every time.