2
$\begingroup$

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?

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

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$.

$\endgroup$
6
  • $\begingroup$ Oh well, you were faster. +1 $\endgroup$ Feb 16 '11 at 19:17
  • $\begingroup$ But if i get above list as input and i need to fill it into the matrix of order NxN in diagonal manner? HOW? $\endgroup$
    – Robertew
    Feb 16 '11 at 19:40
  • $\begingroup$ Please see the updated question. $\endgroup$
    – Robertew
    Feb 16 '11 at 19:43
  • $\begingroup$ @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. $\endgroup$ Feb 16 '11 at 19:44
  • $\begingroup$ @Mariano: thank you for the support.i have edited the qn. $\endgroup$
    – Robertew
    Feb 16 '11 at 19:48
2
$\begingroup$

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)]
$\endgroup$
1
  • $\begingroup$ thanks.can i get the second part too? $\endgroup$
    – Robertew
    Feb 16 '11 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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