Traverse Matrix in Diagonal strips

I thought this problem had a trivial solution, coup开发者_运维百科le 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.

---

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

---

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.

---

Let's take a look how matrix elements are indexed.

(0,0)   (0,1)   (0,2)   (0,3)   (0,4)  
(1,0)   (1,1)   (1,2)   (1,3)   (1,4)  
(2,0)   (2,1)   (2,2)   (2,3)   (2,4)  

Now, let's take a look at the stripes:

Stripe 1: (0,0)
Stripe 2: (0,1)    (1,0)  
Stripe 3: (0,2)    (1,1)    (2,0)
Stripe 4: (0,3)    (1,2)    (2,1)
Stripe 5: (0,4)    (1,3)    (2,2)
Stripe 6: (1,4)    (2,3)
Stripe 7: (2,4)

If you take a closer look, you'll notice one thing. The sum of indexes of each matrix element in each stripe is constant. So, here's the code that does this.

public static void printSecondaryDiagonalOrder(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int maxSum = rows + cols - 2;

    for (int sum = 0; sum <= maxSum; sum++) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i + j - sum == 0) {
                    System.out.print(matrix[i][j] + "\t");
                }
            }
        }
        System.out.println();
    }
}

It's not the fastest algorithm out there (does(rows * cols * (rows+cols-2)) operations), but the logic behind it is quite simple.

---

I found this here: Traverse Rectangular Matrix in Diagonal strips

#include <stdio.h>

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

output:

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

I found this a quite elegant way of doing it as it only needs memory for 2 additonal variables (z1 and z2), which basically hold the information about the length of each slice. The outer loop moves through the slice numbers (slice) and the inner loop then moves through each slice with index: slice - z1 - z2. All other information you need then where the algorithm starts and how it moves through the matrix. In the preceding example it will move down the matrix first, and after it reaches the bottom it will move right: (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3). Again this pattern is captured by the varibales z1 and z2. The row increments together with the slice number untill it reaches the bottom, then z2 will start to increment which can be used to keep the row index constant at it's position: slice - z2. Each slice's length is known by: slice - z1 - z2, perofrming the following: (slice - z2) - (slice - z1 -z2) (minus as the algorithm moves in ascending order m--, n++) results in z1 which is the stopping criterium for the inner loop. Only the column index remains which is conveniently inherited from the fact that j is constant after it reaches the bottom, after which the column index starts to increment.

Preceding algorithm moves only in ascending order from left to right starting at the top left (0,0). When I needed this algorithm I also needed to search through a matrix in descending order starting at the bottom left (m,n). Because I was quite smitten by the algorithm I decided to get to the bottom and adapt it:

• slice length is again known by: slice -z1 - z2
• The starting position of the slices are: (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3)
• The movement of each slice is m++ and n++

I found it quite usefull to depict it as follows:

• slice=0 z1=0 z2=0 (2,0) (column index= rowindex - 2)
• slice=1 z1=0 z2=0 (1,0) (2,1) (column index= rowindex - 1)
• slice=2 z1=0 z2=0 (0,0) (1,1) (2,2) (column index= rowindex + 0)
• slice=3 z1=0 z2=1 (0,1) (1,2) (2,3) (column index= rowindex + 1)
• slice=4 z1=1 z2=2 (0,2) (1,3) (column index= rowindex + 2)
• slice=5 z1=2 z2=3 (0,3) (column index= rowindex + 3)

Deriving the following: j = (m-1) - slice + z2 (with j++) using the expression of the slice length to make the stopping criterium:((m-1) - slice + z2)+(slice -z2 - z1) results into: (m-1) - z1 We now have the argumets for the innerloop: for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)

The row index is know by j, and again we know that the column index only starts incrementing when j starts being constant, and thus having j in the expression again is not a bad idea. From the differences between the above summation I noticed that the difference is always equal to j - (slice - m +1), testing this for some other cases I was confident that this would hold for all cases (I'm not a mathematician ;P) and thus the algorithm for descending movement starting from the bottom left looks as follows:

#include <stdio.h>

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

Now I leave the other two directions up to you ^^ (which is only important when the order is actually important).

This algorithm is quite a mind bender, even when you think you know how it works it can still bite you in the ass. However I think it is quite beautifull because it literally moves through the matrix as you would expect. I am interested if anyone knows more about the algorithm, a name for instance, so I can look if what I have done here actually makes sense and maybe there is a better solutions.

---

I think this can be a solution for any type of matrix.

#include <stdio.h>

#define M 3
#define N 4

main(){
         int a[M][N] = {{1, 2, 3, 4}, 
                        {5, 6, 7, 8}, 
                        {9,10,11,12}};

         int i, j, t;
         for( t = 0; t<M+N; ++t)
              for( i=t, j=0; i>=0 ; --i, ++j)
                     if( (i<M) && (j<N) )
                             printf("%d ", a[i][j]);
         return 0;
}

---

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.

---

// 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;

        }

    }

---

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");
    }   
}   

---

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)

---

Just in case somebody needs to do this in python, it is very easy using numpy:

#M is a square numpy array    
for i in range(-M.shape[0]+1, M.shape[0]):
    print M.diagonal(offset=i)

---

public void printMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    for (int i = 0; i < m + n - 1; i++) {
         int start_row = i < m ? i : m - 1;
         int start_col = i < m ? 0 : i - m + 1;
         while (start_row >= 0 && start_col < n) {
               System.out.print(matrix[start_row--][start_col++]);
         }
         System.out.println("\n")
     }
}

---

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) ...

---

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);
}

---

static int[][] arr = {{ 1, 2, 3, 4},
                      { 5, 6, 7, 8},
                      { 9,10,11,12},
                      {13,14,15,16} };

public static void main(String[] args) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i+1; j++) {
            System.out.print(arr[j][i-j]);
            System.out.print(",");
        }
        System.out.println();
    }

    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < arr.length-i; j++) {
            System.out.print(arr[i+j][arr.length-j-1]);
            System.out.print(",");
        }
        System.out.println();
    }
}

---

A much easier implementation:

//Assuming arr as ur array and numRows and numCols as what they say.
int arr[numRows][numCols];
for(int i=0;i<numCols;i++) {
    printf("Slice %d:",i);
    for(int j=0,k=i; j<numRows && k>=0; j++,k--)
    printf("%d\t",arr[j][k]);
}

---

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    int N = 0;
    cin >> N;

    vector<vector<int>> m(N, vector<int>(N, 0));

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> m[i][j];
        }
    }

    for (int i = 1; i < N << 1; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (j < N && i - j - 1 < N)
            {                          
               cout << m[j][i - j - 1];
            }
        }
        cout << endl;
    }
    return 0;
}

---

A simple python solution

from collections import defaultdict

def getDiagonals(matrix):
    n, m = len(matrix), len(matrix[0])
    diagonals = defaultdict(list)

    for i in range(n):
        for j in range(m):
            diagonals[i+j].append(matrix[i][j])

    return list(diagonals.values())

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

assert getDiagonals(matrix) == [[1], [2, 4], [3, 5, 7], [6, 8], [9]]