zigzag traverse a matrix

I want to traverse a matrix in zig-zag fashion.

Say my matrix is

Code:

---

a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44

---

I want my output to be

Code:

---

a11 a12 a21 a31 a22 a13 a14 a23 a32 a41 a42 a33 a24 a34 a43 a44.

---

Here's how I tried to implement this :

For the upper triangle of the matrix,

(start at 0, 0)
1. move right once
2. move to the bottom left
3. move down once
4. move to the top right.

For the lower triangle of the matrix,

1. move right once
2. move to the top right
3. move down once
4. move to the bottom left.

The code for this works fine but it looks a bit messy and I think it can be optimized. Here's my code for an 8x8 matrix.

Code:

---

  void zigzagOrder()
{
        int i = 0;
        int j = 0;
               
//for upper triangle of matrix
        printf("%d, %d\t", i, j);
        do
        {
                j++;
                printf("\n");
                printf("%d, %d\t", i, j);
                       
                while(j!=0)
                {
                        i++;
                        j--;
                               
                printf("%d, %d\t", i, j);
                        }
                i++;
                if(i>7)
                {
                        i--;
                        break;
                }
                       
                printf("\n");
                printf("%d, %d\t", i, j);

                while(i!=0)
                {
                        i--;
                        j++;
                        printf("%d, %d\t", i, j);
                }
        }
        while(true);
               
//for lower triangle of matrix
        do
        {
                j++;
                printf("\n");
                printf("%d, %d\t", i, j);
                       
                while(j!=7)
                {
                        j++;
                        i--;
                               
                        printf("%d, %d\t", i, j);
                }
                i++;
                if(i>7)
                {
                        i--;
                        break;
                }

                printf("\n");
                printf("%d, %d\t", i, j);

                while(i!=7)
                {
                        i++;
                        j--;
                        printf("%d, %d\t", i, j);
                }
        }
        while(true);
}

---

Please let me know if theres a better way to do this and how I can improve on my code.
Thanks

its quite an interesting little pen&paper exercise to think about the logic, i have not come up with a really neat alternative yet though.
As for improving the code i would certainly use better names for your variables, i personally hate one letter variable names beyond (if i am being lazy) 'x' and 'y' and i will just about tolerate 'i' for iterator, anything else just does my head in and makes things look needlessly complex and harder to read, to the likes of me anyhow.
Also do whiles, while is better for readability for me, unless your structure makes a do while neccesary i would not use it.

There is probably a bit-fiddling trick that could be used for this, but I don't know it.

I can't figure out why you have so many calls to printf(), for just a newline - followed by another call to printf(). Huh? Why not just one call to printf() and put the newline inside the string you're passing to it?

If you want to optimize it for subsequent runs, use this program, with the mods necessary, to make a look up table of pointer (or indeces), in the right zig-zag order, then:

Build your order array, for a very fast run.

Code:

---

int array[] = {11, 12, 21, 31, 22, 13, 14, 23, 32, 41, 42, 33, 24, 34, 43, 44};

for(i=0; i<numElements; i++)
  printf("\n %d, a[array[i]]);

---

Above is about all you'll need at run time. ;)

^^
I will take care of the printfs and the variable names. I used the printfs just for debugging and would not be a part of my final code.

I cannot hard code the order array as my final code wont be limited to an 8x8 matrix.

I actually like Adak's solution a lot, and the good part about it is that it can be generalized. You have to get a piece of paper and a pencil :P and draw a matrix of size nxn where n is unknown. Then start enumerating the positions in order in terms of n like Adak did. Try to identify the pattern by which the indexes change and code it. It's going to take some effort but it's doable.

First run will be A[n-n][n-n] --> STEP 0 (note how n-n + n-n = 0)

second run will be A[n-n][n-n+1], then A[n-n+1][n-n] --> STEP 1 (note how n-n + n-n+1 = 1)

third run will be where you left of, A[n-n+2][n-n], A[n-n+1][n-n+1], A[n-n][n-n+2] --> STEP 2( note how the SUM OF INDICES is the # of the step n-n+2 + n-n = 2, similarly n-n+1 + n-n+1 = 2)

etc.

STEP i: A[n-n+i-0][n-n], A[n-n+i-1][n-n+1], .... A[n-n+i-i][n-n+i]

All you have to do is keep track of whether u r going up or down to figure out the order you are printing them in. For this you need a single flag. When the flag is set to 1, that means you are going up, so start with the left most column i.e. A[n-n+i][n-n] ---- n-n being column 0). If the flag is not set, then you need to start the other way around with the top most row i.e. A[n-n][n-n+i] ---- n-n being row 0.

When you reach the long diagonal, things change slightly in the sense that now, you have an anti-symmetrical situation where the zig-zag starts and ends with the right most column and the bottom most row instead of the first row and first column like above. So figure out how to work the right indexes in that case, and make sure you start decreasing i. i grows as you reach the middle diagonal and decreases afterwards. Basically if in the first half you were going from n-n <--> n-n+i, increasing one and decreasing the other, now you are operating in the range
n-i <--> n-i+i, while i is decreasing from i = n/2 (if n is even) or i=(n+1)/2 (if n is odd) to 0.

Also, make sure you start indexing your arrays from 0 NOT 1. That is just a waste of 2*n elements where n is the size of your matrix. The main difference between programmers and other people is that we count from 0! :)

This sort of array traversal is common in digital signal processing. If the array will always be the same size, you can just create a static lookup table of indexes for traversing in the proper order. If the array width and height are both powers of two, there is a trick you can do with bit manipulation to execute this sort of pattern. For the general case, keep track of row and column independently and "bounce".

In general, this kind of traversal is a modified form of helical interleaving. In true helical interleaving the edges of the matrix "wrap around" and the step size doesn't have to be perfectly diagonal.

@claudiu and Adak - Thanks. I will look into it.

@brewbuck - My array width and height are both always in powers of two. What is the bit manipulation trick I can use?

Thanks

Entropy coding is a special form of lossless data compression. It involves arranging the image components in a "zigzag" order employing run-length encoding (RLE) algorithm that groups similar frequencies together, inserting length coding zeros, and then using Huffman coding on what is left.

Code:

---

void zig_zag()
{
        int siz = 5,k=0;
        cout<<"Please enter the size of the matrix"<<endl;
        cin>>siz;
        int **mat = new int*[siz];
        for(int i = 0; i<siz; i++)
        {
                mat[i] = new int[siz];
                for(int j=0; j<siz; j++)
                        mat[i][j] = ++k;
        }
        int x,y ,z;
        for(z = 0 ; z <siz ; z++)
        {
                x = 0;
                y = z;
                while(x<=z && y>=0)
                {
                        if(z%2)
                                cout<<mat[y--][x++]<<" ";
                        else
                                cout<<mat[x++][y--]<<" ";
                }
                cout<<"\n";
        }
        for(z = 1 ; z<siz ; z++)
        {
                x = z;
                y = siz -1;
                while(x<siz && y>=z)
                {
                        if((siz+z)%2)
                                cout<<mat[x++][y--]<<" ";
                        else
                                cout<<mat[y--][x++]<<" ";
                }
                cout<<"\n";
        }
        for(int i=0;i<siz;i++)
        delete[] mat[i];
        delete[] mat;
}

---

Do you always run around dredging up year old topics to reply to?

Not only that but posting C++ code on a C forum is not the best way to get noticed for your ingenious solutions.