Thread: zigzag traverse a matrix

  1. #1
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53

    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

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    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.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  4. #4
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    ^^
    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.

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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!
    Last edited by claudiu; 03-04-2010 at 01:09 PM.

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    @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

  8. #8
    Registered User
    Join Date
    Jan 2011
    Posts
    1
    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;
    }

  9. #9
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Do you always run around dredging up year old topics to reply to?

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Not only that but posting C++ code on a C forum is not the best way to get noticed for your ingenious solutions.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  3. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM
  4. Matrix and vector operations on computers
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-11-2004, 06:36 AM