algorithm needed
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 41

Thread: algorithm needed

  1. #1
    Join Date
    Dec 2003
    Location
    indiana
    Posts
    21

    Question algorithm needed

    hi, i need algorithm to read the elements of an 8 x 8 matrix in a zigzag way. and also want the antizigzag algorithm to recover the elements.

    i am giving link below..... that will show how actually i want to read the elemnts of the matrix.

    http://www.ascc.net/nl/84/1110/05.html

    there is a figure which shows the zigzag scan.

    can you suggest any algorithm how to read and recover (anti zigzag) the elements in that way???

    thanks

  2. #2
    Join Date
    Dec 2003
    Location
    indiana
    Posts
    21
    let me put my question in a simpler way,i have a 8 x 8 matrix.... from that matrix i want to read the elements like the link below and want to store in a 1-D buffer .

    http://www.ascc.net/nl/84/1110/turn.gif

    of course the elements could be anything(positive/negative/fraction)



    can anybody suggest algorithm/pseuodocode plz

  3. #3
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    There is a function used to show that NxN has the same
    cardinality as N (Here N is the set of natural numbers starting at
    zero)
    consider a point in NxN, <m,n>, then
    f(m,n) = 1/2[(m+n)^2 +3m+n] defines a one-to-one onto relationship
    between the desired sets.

    This function "moves" in the zig-zag pattern you want.

    so given an 8x8 matrix (however you implement that) I will
    assume you access it as your_matrix[m][n], then the assignement
    to a vector would be
    first you need to compute a number
    int j = (7 >= m+n ? 0:(m+n - 7));
    for(int i = 1; i < (7 >= m+n ? 0:(m+n - 7)); i++)
    j += 2i ;

    your_vector[1/2((m+n)^2 +3m+n) - j] = your_matrix[m][n]

    any way this is the idea
    Last edited by souldog; January 1st, 2004 at 04:36 AM.
    Wakeup in the morning and kick the day in the teeth!! Or something like that.

    "i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."

  4. #4
    Join Date
    Dec 2003
    Posts
    99
    Looks like you are involved some way in image codecs.

    In so, the better way is to have another 8x8 matrix for storing appropriate indexes.

    for eg for 4x4 matrix you would have used the following
    4x4 matrix

    Zig Zag Seq:

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

    Index Matrix
    0 1 4 8
    5 2 3 6
    9 10 7 11

    Then the loop will be
    for (i=0 to 7
    j= 0 to 7
    Array[i * 8 + j] = Matrix[Index[i][j]]

    Atleast the idea is correct

    Regards

  5. #5
    Join Date
    Dec 2003
    Location
    indiana
    Posts
    21
    hi souldog,
    your given function is interesting. but it is not giving me the correct result.

    i wrote a small code for this.......

    Code:
    #include<stdio.h>
    
    int main()
    
    {
    int  my_vector[65];//buffer
    int  my_matrix[8][8] =           {		{ 0,1,5,6,14,15, 27, 28  },
    
                                            { 2,4,7,13,16,26,29,42},
    
                                            { 3,8,12,17,25,30,41,43},
    
                                            { 9,11,18,24,31,40,44,53},
    
                                            { 10,19,23,32,39,45,52,54},
    
                                            {  20,22,33,38,46,51,55,60},
    
                                            {  21,34,37,47,50,56,59,61},
    
                                            { 35,36,48,49,57,58,62,63}
    
                                    };
    
    
    
    
    
    
    for(int m=0;m<7;m++)
    
    for(int n =0;n<7;n++)
    
    {
    
      int j = (7 >= m+n ? 0 : (m+n - 7));
      for(int i = 1; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
      j += 2*i ;
    
      my_vector[((m+n)*(m+n)+3*m+n)/(2) - j] = my_matrix[m][n];
    
    }
    
    for(m=0;m<64;m++) printf("%d\n",my_vector[m]);
    
    
    
    return 0;
    
    }

    if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????


    To nsh123
    -----------------------

    although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.


    plz can you explain more by a small code??

    thanks

  6. #6
    Join Date
    Dec 2003
    Posts
    99
    To nsh123
    -----------------------
    although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.

    plz can you explain more by a small code??
    You are perfectly on track !!!
    The code posted earlier is exactly what is required.
    To make it more clear:
    You were trying to generate the zig-zag sequence algorithmically
    And I have suggested to hard-code it in your code itself in the form of 8x8 matrix.
    Ofcourse assuming 8x8 the only type you deal with.


    Regards,

  7. #7
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    Thats is because your indices are wrong.
    I made the change ion the code below

    The function works, but It could be cleaned up a bit.

    Originally posted by maxima
    hi souldog,
    your given function is interesting. but it is not giving me the correct result.

    i wrote a small code for this.......

    Code:
    #include<stdio.h>
    
    int main()
    
    {
    int  my_vector[65];//buffer
    int  my_matrix[8][8] =           {		{ 0,1,5,6,14,15, 27, 28  },
    
                                            { 2,4,7,13,16,26,29,42},
    
                                            { 3,8,12,17,25,30,41,43},
    
                                            { 9,11,18,24,31,40,44,53},
    
                                            { 10,19,23,32,39,45,52,54},
    
                                            {  20,22,33,38,46,51,55,60},
    
                                            {  21,34,37,47,50,56,59,61},
    
                                            { 35,36,48,49,57,58,62,63}
    
                                    };
    
    
    
    
    
    
    for(int m=0;m<8;m++)   //CHANGE UPPER LIMIT TO EIGHT
    
    for(int n =0;n<8;n++)  //CHANGE UPPER LIMIT TO EIGHT
    
    {
    
      int j = (7 >= m+n ? 0 : (m+n - 7));
      for(int i = 1; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
      j += 2*i ;
    
      my_vector[((m+n)*(m+n)+3*m+n)/(2) - j] = my_matrix[m][n];
    
    }
    
    for(m=0;m<64;m++) printf("%d\n",my_vector[m]);
    
    
    
    return 0;
    
    }

    if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????


    To nsh123
    -----------------------

    although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.


    plz can you explain more by a small code??

    thanks
    Wakeup in the morning and kick the day in the teeth!! Or something like that.

    "i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."

  8. #8
    Join Date
    Nov 2003
    Posts
    1,405
    This is a prodecural approach using stepwise refinement.

    Say you have two indexes i and j. The start condition is i=j=0 and the end condition is i=j=7. The indexes can 'move' in two diagonal directions diag_up and diag_down. There are four 'borders' that can be reached border_1 to border_4. When a border is reach the indexes can be advanced in four ways, advance_1 to advance_4 and the direction changes.

    In pseudo code this translates to,
    Code:
    boolean up = true;    // direction
    int i=j=0;    // start
    while (!(i == 7) && (j ==7 )) {     // stop
       if (border_1()) {            // a border is reached
           advance_1(); up = !up; // advance and change direction
       } else if (border_2()) {
           advance_2(); up = !up;
       } else if (border_3()) {
           advance_3(); up = !up;
       } else if (border_4()) {
           advance_4(); up = !up;
       } else {                             // no border
          if (up) diag_up(); else diag_down(); // cont. is same dir.
       }
    }
    What remains is to identify the actual index increments/decrements. For example diag_up is i++, j--. Lim_1 is j==0. Advance_1 is i++.

  9. #9
    Join Date
    Nov 2003
    Posts
    1,405
    Originally posted by _uj
    This is a prodecural approach using stepwise refinement.
    Well, this is the first refinement. You have to change the pseudocode a little because you can reach two borders at the same time. As a matter of fact one such two-border position constitutes the end criteria.

  10. #10
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863
    Well, I have already given the function which will do what
    the op wants, if he/she can manage to implement the code.

    however, I would recommend using nsh123's suggestion and
    just implement some lookup tables.
    Wakeup in the morning and kick the day in the teeth!! Or something like that.

    "i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."

  11. #11
    Join Date
    Nov 2003
    Posts
    1,405
    This is a simple to understand procedural version. Say you have an 8x8 chessboard. You start in the 0,0 position then you walk diagonal up. If you land outside the chessboard you correct the position and change walking direction. You can land outside the chessboard in 5 different places,
    Code:
    int d=1;	// start direction (diagonal up)
    int i=0, j=0; // index
    for (int k=0; k<64; k++) { // all chessboard squares
    	// TRACE(STR(k) + ":" + STR(i) + "/" + STR(j));
                    output_buffer[k] = chess_board[i,j];
    	i += d; // next index positions
    	j -= d;
    	if (j < 0) { // outside top
    		j = 0;
    		d = -d; // change direction
    	} else if (i < 0) {
    		if (j > 7) { // outside left and bottom
    			j = 7;
    			i += 2;
    		} else {	// outside left
    			i = 0;			
    		}
    		d = -d;
    	} else if (i > 7) { // outside right
    		i = 7;
    		j += 2;
    		d = -d;
    	} else if (j > 7) { // outside bottom
    		j = 7;
    		i += 2;
    		d = -d;
    	}
    }

  12. #12
    Join Date
    Dec 2003
    Location
    indiana
    Posts
    21
    To souldog
    -----------
    yes...i did mistake in the limit.....now its working... thanks


    chessboard algorithm given by ._uj is also good but i have to think about chessboard algorithm a little bit.


    To nash
    ------------------
    i think nash's suggestion would be the simplest one .

    so, i want to implement that....... but getting some trouble.

    i am writing below what i am thinking.

    Code:
                                                                                                            
    
    my_matrix[8][8] =  
    
    
         | 30   0   0   0   0   0   0   0|
         | -7   8   1   1   0   0   0   0|
         |-11   6   0   1   0   0   0   0|
         | -5  -3   0   0   0   0   0   0|
         | -7  -3   2   0   0   0   0   0|
         | -4   4   0   0   0   0   0   0|
         | -1   0   1   0   0   0   0   0|
         | -3   1   0   0   0   0   0   0|
     
                     
    
    
    my_index[8][8] =       
    
    
         |  1 |  2 |  6 |  7 | 15 | 16 | 28 | 29 |
        
         |  3 |  5 |  8 | 14 | 17 | 27 | 30 | 43 |
         
         |  4 |  9 | 13 | 18 | 26 | 31 | 42 | 44 |
         
         | 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |
        
         | 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |
         
         | 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |
         
         | 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |
        
         | 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |
              
                                              
    // my_index[8][8] is the look up table/zigzag table  that u r suugesting.
    
     your quote
    
    Then the loop will be for (i=0 to 7 j= 0 to 7 Array[i * 8 + j] = Matrix[Index[i][j]]
    can you explicitly tell me which way i would fetch the elements form the my_matrix[][] by looking index table?????
    as you know i am expecting in my buffer[] this sequence(i.e zigzag)
    30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0
    0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

  13. #13
    Join Date
    Nov 2003
    Location
    Belgium
    Posts
    8,062
    You my_index matrix is wrong, look at nsh's post again.

  14. #14
    Join Date
    Nov 2003
    Posts
    1,405
    Originally posted by maxima
    chessboard algorithm given by ._uj is also good but i have to think about chessboard algorithm a little bit.
    I've run the chessboard algoritm with your index matrix. If you run the code snippet below you'll see that the elements come out in the expected order, namely: 1,2,3, ....... 63,64. Now you just have to plug in my_matrix instead and assign the elements to a 64 element int array using the k index. Use it if you like, it does the expected.
    Code:
    int my_index[8][8] =
    {{1 ,  2 ,  6 ,  7 , 15 , 16 , 28 , 29},
    {3 ,  5 ,  8 , 14 , 17 , 27 , 30 , 43},
    {4 ,  9 , 13 , 18 , 26 , 31 , 42 , 44},
    {10 , 12 , 19 , 25 , 32 , 41 , 45 , 54},
    {11 , 20 , 24 , 33 , 40 , 46 , 53 , 55},
    {21 , 23 , 34 , 39 , 47 , 52 , 56 , 61},
    {22 , 35 , 38 , 48 , 51 , 57 , 60 , 62},
    {36 , 37 , 49 , 50 , 58 , 59 , 63 , 64}};
    for (int d=1,i=0,j=0,k=0; k<64; k++) { // all chessboard squares
    	TRACE(STR(my_index[j][i]));	// println
    	i += d; // next index positions
    	j -= d;
    	if (j < 0) { // outside top
    		j = 0;
    		d = -d; // change direction
    	} else if (i < 0) {
    		if (j > 7) { // outside left and bottom
    			j = 7;
    			i += 2;
    		} else {	// outside left
    			i = 0;			
    		}
    		d = -d;
    	} else if (i > 7) { // outside right
    		i = 7;
    		j += 2;
    		d = -d;
    	} else if (j > 7) { // outside bottom
    		j = 7;
    		i += 2;
    		d = -d;
    	}
    }
    PS. TRACE and STR are just a way to print numbers.

    To make the algoritm general and work for all 'chessboard' sizes like 9x9 you'll have to take care of the 'outside right and top' case too which would be easy.

  15. #15
    Join Date
    Dec 2003
    Location
    indiana
    Posts
    21
    To souldog
    -----------
    yes...i did mistake in the limit.....now its working... thanks
    i am sorry.....its not working properly. only changing the index will not be sufficient .... i checked again.....somewher there is some problem......



    To _uj
    ------------------

    yes it is going into buffer in the correct way... but i want to reconstruct the matrix from the buffer again...

    ok what i wrote giving below...

    Code:
    #include<stdio.h>
    
    int main()
    
    {
    
    
    
    int output_buffer[64]; 
    
    
    int new_matrix[8][8];
    
    
    
    
    int my_index[8][8] =
    {{1 ,  2 ,  6 ,  7 , 15 , 16 , 28 , 29},
    {3 ,  5 ,  8 , 14 , 17 , 27 , 30 , 43},
    {4 ,  9 , 13 , 18 , 26 , 31 , 42 , 44},
    {10 , 12 , 19 , 25 , 32 , 41 , 45 , 54},
    {11 , 20 , 24 , 33 , 40 , 46 , 53 , 55},
    {21 , 23 , 34 , 39 , 47 , 52 , 56 , 61},
    {22 , 35 , 38 , 48 , 51 , 57 , 60 , 62},
    {36 , 37 , 49 , 50 , 58 , 59 , 63 , 64}};
    
    for (int d=1,i=0,j=0,k=0; k<64; k++) 
    
    { 
      output_buffer[k]  = my_index[j][i];	
    	i += d;
    	j -= d;
    	if (j < 0) { 
    		j = 0;
    		d = -d; // change direction
    	} else if (i < 0) {
    		if (j > 7) { // outside left and bottom
    			j = 7;
    			i += 2;
    		} else {	// outside left
    			i = 0;			
    		}
    		d = -d;
    	} else if (i > 7) { // outside right
    		i = 7;
    		j += 2;
    		d = -d;
    	} else if (j > 7) { // outside bottom
    		j = 7;
    		i += 2;
    		d = -d;
    	}
    }
    
    
    for( k=0;k<64;k++)
    printf("%d\t",output_buffer[k]);
    
    
    
    printf("\n\n\n");
    
    
    
    
    
    /* ---reconstruction of the matrix  from the output buffer -----------------*/
    
    // this part(anti-zigzag ) is not  reconstructing the matrix.
    
    
    for ( d=1,i=0,j=0,k=0; k<64; k++) 
    
    { 
      new_matrix[j][i] = output_buffer[k];	
    	i += d;
    	j -= d;
    	if (j < 0) { 
    		j = 0;
    		d = -d; // change direction
    	} else if (i < 0) {
    		if (j > 7) { // outside left and bottom
    			j = 7;
    			i += 2;
    		} else {	// outside left
    			i = 0;			
    		}
    		d = -d;
    	} else if (i > 7) { // outside right
    		i = 7;
    		j += 2;
    		d = -d;
    	} else if (j > 7) { // outside bottom
    		j = 7;
    		i += 2;
    		d = -d;
    	}
    }
    
    
    
    for(i=0;i<8;i++)
    
    {
    	for(j=0;j<8;j++)
    
     {
    	 printf("%d\t",new_matrix[j][i]);
    
     }
    
     printf("\n");
     
    }
    
    
    
    
    }

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center