Traverse Matrix in Diagonal strips

Question

I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated.

So my question is, how would you write (in C) a function traversal of a square matrix in diagonal strips.

Example:

1  2  3
4  5  6
7  8  9

Would have to be traversed in the following order:

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

Each strip above is enclosed by square brackets. One of the requirements is being able to distinguish between strips. Meaning that you know when you're starting a new strip. This because there is another function that I must call for each item in a strip and then before the beginning of a new strip. Thus a solution without code duplication is ideal.

Answer 1

The key is to iterate every item in the first row, and from it go down the diagonal. Then iterate every item in the last column (without the first, which we stepped through in the previous step) and then go down its diagonal.

Here is source code that assumes the matrix is a square matrix (untested, translated from working python code):

#define N 10
void diag_step(int[][] matrix) {
    for (int i = 0; i < N; i++) {
     int j = 0;
     int k = i;
     printf("starting a strip\n");
     while (j < N && i >= 0) {
      printf("%d ", matrix[j][k]);
      k--;
      j++;
     }
     printf("\n");
    }

    for (int i = 1; i < N; i++) {
     int j = N-1;
     int k = i;
     printf("starting a strip\n");
     while (j >= 0 && k < N) {
      printf("%d ", matrix[k][j]);
      k++;
      j--;
     }
     printf("\n");
    } 
}

Answer 2

Pseudo code:

N = 2 // or whatever the size of the [square] matrix
for x = 0 to N
  strip = []
  y = 0
  repeat
     strip.add(Matrix(x,y))
     x -= 1
     y -= 1
  until x < 0
  // here to print the strip or do some' with it

// And yes, Oops, I had missed it... 
// the 2nd half of the matrix...
for y = 1 to N    // Yes, start at 1 not 0, since main diagonal is done.
   strip = []
   x = N
   repeat
      strip.add(Matrix(x,y))
      x -= 1
      y += 1
   until x < 0
  // here to print the strip or do some' with it

(Assumes x indexes rows, y indexes columns, reverse these two if matrix is indexed the other way around)

Answer 3

I thought this problem had a trivial solution, couple of for loops and some fancy counters

Precisely.

The important thing to notice is that if you give each item an index (i, j) then items on the same diagonal have the same value j+n–i, where n is the width of your matrix. So if you iterate over the matrix in the usual way (i.e. nested loops over i and j) then you can keep track of the diagonals in an array that is addressed in the above mentioned way.

Answer 4

Here's something you can use. Just replace the printfs with what you actually want to do.

#include <stdio.h>

int main()
{
    int x[3][3] = {1, 2, 3,
                   4, 5, 6,
                   7, 8, 9};
    int n = 3;
    for (int slice = 0; slice < 2 * n - 1; ++slice) {
     printf("Slice %d: ", slice);
     int z = slice < n ? 0 : slice - n + 1;
     for (int j = z; j <= slice - z; ++j) {
      printf("%d ", x[j][slice - j]);
     }
     printf("\n");
    }
    return 0;
}

Output:

Slice 0: 1
Slice 1: 2 4
Slice 2: 3 5 7
Slice 3: 6 8
Slice 4: 9

Answer 5

hi

you have to break the matrix in to upper and lower parts, and iterate each of them separately, one half row first, another column first. let us assume the matrix is n*n, stored in a vector, row first, zero base, loops are exclusive to last element.

for i in 0:n
    for j in 0:i +1
        A[i + j*(n-2)]

the other half can be done in a similar way, starting with:
for j in 1:n
    for i in 0:n-j
        ... each step is i*(n-2) ...

Answer 6

I would shift the rows like so:

1  2  3  x  x
x  4  5  6  x
x  x  7  8  9

And just iterate the columns. This can actually be done without physical shifting.

Answer 7

I would probably do something like this (apologies in advance for any index errors, haven't debugged this):

// Operation to be performed on each slice:
void doSomething(const int lengthOfSlice,
                 elementType *slice,
                 const int stride) {
    for (int i=0; i<lengthOfSlice; ++i) {
        elementType element = slice[i*stride];
        // Operate on element ...
    }
}

void operateOnSlices(const int n, elementType *A) {
    // distance between consecutive elements of a slice in memory:
    const int stride = n - 1;

    // Operate on slices that begin with entries in the top row of the matrix
    for (int column = 0; column < n; ++column)
        doSomething(column + 1, &A[column], stride);

    // Operate on slices that begin with entries in the right column of the matrix
    for (int row = 1; row < n; ++row)
        doSomething(n - row, &A[n*row + (n-1)], stride);
}

Answer 8

// This algorithm works for matrices of all sizes. ;)

    int x = 0;
    int y = 0;        
    int sub_x;
    int sub_y;

    while (true) {

        sub_x = x;
        sub_y = y;

        while (sub_x >= 0 && sub_y < y_axis.size()) {

            this.print(sub_x, sub_y);
            sub_x--;
            sub_y++;

        }

        if (x < x_axis.size() - 1) {

            x++;

        } else if (y < y_axis.size() - 1) {

            y++;

        } else {

            break;

        }

    }