Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am having an NxN matrix . I want to read the elements of that NxN matrix diagonally and need to store it in an array.How?

For example, I am having one 3x3 matrix

$$\begin{bmatrix} A B C \\ D E F\\ G H I \end{bmatrix}$$

I want to read this matrix diagonally(starting from A and downwards) and output should be

A D B C E G H F I

Update:

How can i do it in reverse manner?

I want to fill the above read array(A D B C E G H F I) into an NxN (N should be given as input) HOW?

share|improve this question
1  
Hint: Note that on a diagonal as you define it, the sum of the indices of an array component is always the same. –  Raskolnikov Feb 16 '11 at 18:43
    
can i get the logic in an equation form? –  Robertew Feb 16 '11 at 18:57
    
OK, I'll cook something up, just give me some time. –  Raskolnikov Feb 16 '11 at 19:03
    
OK sure. I am waiting for your reply. Finally I am implementing the logic using C langauage. –  Robertew Feb 16 '11 at 19:32
2  
in any case, this is not a mathematical question: you should have asked on the programming site... –  Mariano Suárez-Alvarez Feb 16 '11 at 19:43
add comment

2 Answers

The array is made in such a way that the elements whose row position + column posiiton are clumped together, in an increasing order. That is, all the elements $a_{ij}$ such that $i + j = k$ will form a "group" of elements in the array.

$$\begin{pmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{pmatrix}$$

will give the list

$$( \underbrace{a_{11}}_{i+j = 2} , \underbrace{a_{21} , a_{12}}_{i+j = 3} , \underbrace{a_{13} , a_{22} , a_{31}}_{i+j=4} , \underbrace{a_{41} , a_{32} , a_{23} , a_{14}}_{i+j = 5} , \underbrace{a_{24} , a_{33} , a_{42} }_{i+j = 6} , \underbrace{a_{43} , a_{34}}_{i+j = 7} , a_{44} )$$

This shows a systematic way you can do it. Iterate through the $k$. When you get to a new $k$, increase the largest of the $i,j$ if you can, otherwise increase the smallest, so you get $i+j = k$. Then decrease the largest of the two and increase the smallest of the two until you have the reverse (that is, the one that was the largest to begin with is now 1). Restart.

Note also that you have a symmetry, you will have two groups with the same size for every size except $k = n+1$, which might be used to improve the algorithm.

EDIT: To reverse the process, start with $p = 1$ and iterate $p$ to $n$, then decrease it back to $1$ in a loop (or two loops maybe).

Every time you go through the loop, take $p$ elements from the list, let's call them $a_1, a_2, \dots, a_p$, and put them in the matrix. To do this, use two variables $i$ and $j$. At the start of every iteration of the loop, $i$ and $j$ have the values of the element last inserted. Increase the largest value by 1, if you can (when $p$ is increasing), otherwise increase the smallest value. Stepwise reverse the numbers as before, inserting the elements $a_1, a_2, \dots, a_p$.

share|improve this answer
    
Oh well, you were faster. +1 –  Raskolnikov Feb 16 '11 at 19:17
    
But if i get above list as input and i need to fill it into the matrix of order NxN in diagonal manner? HOW? –  Robertew Feb 16 '11 at 19:40
    
Please see the updated question. –  Robertew Feb 16 '11 at 19:43
    
@Robertew: this comment of yours asks a different question that the one you originally asked. If you intend to ask both, please do edit the original question to include the two. –  Mariano Suárez-Alvarez Feb 16 '11 at 19:44
    
@Mariano: thank you for the support.i have edited the qn. –  Robertew Feb 16 '11 at 19:48
show 1 more comment

You can do something like the following Haskell code:

walk (n, m) = step (1,-1) (1,1)
  where step (dx, dy) (x, y) 
          | (x, y) == (n, m)                    = [(x, y)]
          | (x' == 0 && y' <= m) || x' == n + 1 = (x, y) : step (-dx, -dy) (x, y + 1)
          | (y' == 0 && x' <= n) || y' == m + 1 = (x, y) : step (-dx, -dy) (x + 1, y)
          | otherwise                           = (x, y) : step (dx, dy) (x', y')
          where x' = x + dx
                y' = y + dy

with that definition, we have for example

*Main> walk (3,4)
[(1,1),(2,1),(1,2),(1,3),(2,2),(3,1),(3,2),(2,3),(1,4),(2,4),(3,3),(3,4)]
share|improve this answer
    
thanks.can i get the second part too? –  Robertew Feb 16 '11 at 19:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.