wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Convert Row Major rep to Column Major rep
        
(Message started by: sateesp on Aug 22^nd, 2010, 3:53am)

Title: Convert Row Major rep to Column Major rep
Post by sateesp on Aug 22^nd, 2010, 3:53am

Given M*N matrix is represented in row major fashion in single dimension array. Write a Algo to convert this array into column major way of representation of matrix.
Example: Given matrix
1 2 3 4
5 6 7 8
and array connects are 1 2 3 4 5 6 7 8. Now we need to convert to 1 5 2 6 3 7 4 8

Title: Re: Convert Row Major rep to Column Major rep
Post by towr on Aug 22^nd, 2010, 6:38am

Do you want to rearrange it in the same memory without using extra memory to do so?

Title: Re: Convert Row Major rep to Column Major rep
Post by sateesp on Aug 22^nd, 2010, 10:44am

yes towr.

Title: Re: Convert Row Major rep to Column Major rep
Post by TenaliRaman on Aug 23^rd, 2010, 7:01am

No extra memory might be a bit harsher restriction as per [1] (for arbitrary rectangular matrices).

However, it is possible to do in-place transposition for square matrices with no extra memory [1].

If you allow for O(1) memory at least, then there are some neat cycle based algorithms given in [1].

-- AI
[1] http://en.wikipedia.org/wiki/In-place_matrix_transposition

Title: Re: Convert Row Major rep to Column Major rep
Post by sateesp on Aug 23^rd, 2010, 9:19am

Yes, constant space is allowed.
@TenaliRaman,I just saw wiki link you provided. It has very good explanation. Thanks.