Author |
Topic: Convert Row Major rep to Column Major rep (Read 2834 times) |
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Convert Row Major rep to Column Major rep
« on: Aug 22nd, 2010, 3:53am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Convert Row Major rep to Column Major rep
« Reply #1 on: Aug 22nd, 2010, 6:38am » |
Quote Modify
|
Do you want to rearrange it in the same memory without using extra memory to do so?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Convert Row Major rep to Column Major rep
« Reply #2 on: Aug 22nd, 2010, 10:44am » |
Quote Modify
|
yes towr.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Convert Row Major rep to Column Major rep
« Reply #3 on: Aug 23rd, 2010, 7:01am » |
Quote Modify
|
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
|
| « Last Edit: Aug 23rd, 2010, 7:32am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Convert Row Major rep to Column Major rep
« Reply #4 on: Aug 23rd, 2010, 9:19am » |
Quote Modify
|
Yes, constant space is allowed.
@TenaliRaman,I just saw wiki link you provided. It has very good explanation. Thanks.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print