Traverse Matrix in Diagonal strips

49,413

Solution 1

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

Solution 2

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.

Solution 3

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.

Solution 4

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.

Solution 5

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;
}
Share:
49,413
alyx
Author by

alyx

Updated on February 12, 2021

Comments

  • alyx
    alyx about 3 years

    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.

  • Mark Byers
    Mark Byers over 14 years
    This doesn't seem to cover the second half of the matrix.
  • dwc
    dwc over 14 years
    This is DRY, but not easy to follow at all
  • mjv
    mjv over 14 years
    @Mark B Thanks for noting that! Proves that nothing is fully trivial, sloppy me!
  • vprajan
    vprajan almost 13 years
    Beautiful logic!!.. if you want to traverse the reverse side i.e, from top-right corner of the matrix, just change slice-j to (n-1)-slice-j.
  • vprajan
    vprajan almost 13 years
    @coder, i don't know what case didn't work for you.. did you miss the brackets ? its (n-1)-(slice-j), slice always >0.. check here: analgorithmaday.blogspot.com/2011/04/…
  • sharoz
    sharoz over 12 years
    Thanks for not assuming that width and height would always be identical!
  • Alpha Mineron
    Alpha Mineron over 5 years
    Nice explanation but some improvement could help. Ex: "In the preceding example it will move ..... bottom it will move right", This is wrong as the algorithm isn't transversing through the matrix actively in each step as your use of words "It'll move" suggest. Instead, you should've mentioned that it goes through the diagonal slice at every increment of slice and then moves down. A slight change but can lead to major misleading. Plus, I believe you did too much work on your second part. You simply had to introduce (m-1) or (n-1) in the respective indices to invert the directions.
  • Evgeni Nabokov
    Evgeni Nabokov almost 4 years
    without physical shifting // Implementation?