Traverse Matrix in Diagonal strips
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.