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.

Answer 2

(non-checked code) Something like this (java code):

// suppose m is the matrix, so basically an int[][] array with r rows and c columns
// m is an int[rows][cols];

List result = new ArrayList(rows + cols - 1);
for (int i = 0; i < (rows + cols - 1))
{
  int y;
  int x;
  if (i < rows)
  {
    x = 0;
    y = rows - i - 1;
  }
  else
  {
    x = i - rows + 1;
    y = 0;
  }
  Vector v = new Vector();
  while (y < rows && x < cols)
  {
    y++;
    x++;
    v.add(new Integer(m[y][c]));
  }
  result.add(v);
}
// result now contains the vectors you wanted

Edit: i had x and y mixed up, corrected now.

Answer 3

Mathematica:

m = {{6, 0, 3, 5}, 
     {3, 7, 1, 4}, 
     {1, 4, 8, 2}, 
     {0, 2, 5, 9}};

Table[Diagonal[m, i], {i, 1 - Length@m, Length@m[[1]] - 1}]

Which gives a list of the i'th diagonals where the 0th diagonal is the main diagonal, i = -1 gives the one below it, etc. In other words, it returns:

{{0}, {1, 2}, {3, 4, 5}, {6, 7, 8, 9}, {0, 1, 2}, {3, 4}, {5}}

Of course using the built-in Diagonal function is kind of cheating. Here's an implementation of Diagonal from scratch:

(* Grab the diagonal starting from element (i,j). *)
diag0[m_,i_,j_] := Table[m[[i+k, j+k]], {k, 0, Min[Length[m]-i, Length@m[[1]]-j]}]

(* The i'th diagonal -- negative means below the main diagonal, positive above. *)
Diagonal[m_, i_] := If[i < 0, diag0[m, 1-i, 1], diag0[m, 1, i+1]]

The Table function is basically a for loop that collects into a list. For example,

Table[2*i, {i, 1, 5}]

returns {2,4,6,8,10}.