This week's book giveaway is in the Jobs Discussion forum. We're giving away four copies of Java Interview Guide and have Anthony DePalma on-line! See this thread for details.

I am wondering how to transpose a matrix (m * n) with only constant space complexity O (1). (The transpose algorithm should execute/operate on the original matrix.)

Firstly, how are you storing your matrix - as a 2-dimensional array, a collection of objects or something else?

I don't think it is possible to do an O(1) transposition, unless you've got some clever OO mechanism which can simply relabel a row as a column and vice-versa. Even then, you'll have n rows/m columns to relabel, so the order of complexity will not be constant and will depend on the size of matrix. Probably the best you will get is O(log[n]), which I think only applies when the matrix is square? The 'blind' algorithm takes an [n][m] array and converts all entries to the [m][n] transposed array, using two loops, and will get you at worst O(n^2).

Try Googling around for matrix transposition algorithms; failing that, I'm sure there are books on the subject (probably covering hundreds of pages just for this one algorithm!)

Good luck! [ January 07, 2006: Message edited by: Charles Lyons ]

Charles Lyons (SCJP 1.4, April 2003; SCJP 5, Dec 2006; SCWCD 1.4b, April 2004)
Author of OCEJWCD Study Companion for Oracle Exam 1Z0-899 (ISBN 0955160340 / AmazonAmazon UK )

do you need to PHYSICALLY transpose the matrix? or do you just need to ACCESS the transposed matrix?

if you need (for some reason) to actually move the elements around, you can't do it in O(1).

But if all you have to do is access an element of the transposed matrix, then Steve has given you the answer.

What is a transposed matrix? it is the matrix created when every element at (x,y) gets moved to position (y,x). so really, all you have to do is access the elements in a different way, and you're done.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

George Lin
Ranch Hand

Joined: Jan 11, 2005
Posts: 125

posted

0

Steve,

Originally posted by Steve Fahlbusch: Assuming that you have some implemenation of matrix that will allow for direct access to any element. So you have an accessor:

getElement( i, j )

Which will return the ith,jth element of the matrix: return matrix( i, j )

change that to:

Your idea is very smart! But I need to transpose the matrix in-place other than from output level (showed in your sample).

Do you have any good ideas?

regards, George

George Lin
Ranch Hand

Joined: Jan 11, 2005
Posts: 125

posted

0

fred,

Originally posted by fred rosenberger: do you need to PHYSICALLY transpose the matrix? or do you just need to ACCESS the transposed matrix?

if you need (for some reason) to actually move the elements around, you can't do it in O(1).

But if all you have to do is access an element of the transposed matrix, then Steve has given you the answer.

What is a transposed matrix? it is the matrix created when every element at (x,y) gets moved to position (y,x). so really, all you have to do is access the elements in a different way, and you're done.

Thank you very much for your reply!

I need to transpose the matrix PHYSICALLY in-place. When mentioning O(1), I mean the space complexity is O(1) -- not the time complexity.

Do you have any good ideas?

regards, George

George Lin
Ranch Hand

Joined: Jan 11, 2005
Posts: 125

posted

0

Charles,

Originally posted by Charles Lyons: Firstly, how are you storing your matrix - as a 2-dimensional array, a collection of objects or something else?

I don't think it is possible to do an O(1) transposition, unless you've got some clever OO mechanism which can simply relabel a row as a column and vice-versa.

About the storage data structure -- we can use any common data structure if transpose operation can be completed with only O(1) space complexity.

I think you mid-understand my problem a bit -- when mentioning O(1), I mean the space complexity, not the time complexity.

regards, George

Charles Lyons
Author
Ranch Hand

Joined: Mar 27, 2003
Posts: 836

posted

0

My apologies - mostly the talk is about time complexity because memory is so cheap these days, so naturally I assumed this was your intention!

Now, I'm a little rusty on complexities, so please say if I'm talking rubbish. O(1) space complexity means the algorithm uses the same amount of storage memory space regardless of how large the input is.

I'm going to assume you're using a 2-dimensional array to store the data, and since that array could be of any datatype, I'll call it "Arr[][]". I'll let the first dimension be the rows, and the second the columns within each row. For an m x n matrix we therefore have Arr[m][n]. Clearly this array will have to be as large the matrix, and therefore will occupy more memory space for larger input - but this isn't the fault of the algorithm (only the input).

To be honest, I can't see a way to transpose a general m x n matrix without having a second Arr[n][m] array to put it in. We cannot dereference the first array to resize it, then reference its entries! We would have to have two arrays in memory.

However, we can optimise for a square n x n array with data Arr[n][n], since they we don't have to change the sizes of each dimension. We can create an O(1) space algorithm by swapping entries on either side of the principle diagonal, and I think this sketch should do it:

I think that should give O(1) space complexity - we are only declaring i, j and swap for each iteration, and these will always be declared for any size array. In addition, we only have swap for those entries above the diagonal, which is significantly less than half the matrix - for an n x n this is actually n*(n-1)/2.

The time complexity of this algorithm is O(n^2), making it inefficient. As I said previously, there are O(log[n]) algorithms, but they use caching of pieces of the matrix for efficiency, and this increases the space complexity. I would think this trade-off is probably worthwhile in the long-run.

I'm not so sure about the general m x n problem - please repost if you can clarify or have any further ideas...

there are many ways of accomplishing this and since this is not a real problem (ie: this is a made-up homework assignment) why don't you post the full requirements, that way we can address you solution to the problem statement.

For instance, if this is for a data structures course the approach might be much differnt than an algorithms course. (and my previous posts reflected an approach i would expect from my students, but lets see what is expected).

It's quite interesting how the entries in this thread are pretty much the same as the entries in another thread on the Sun Java forum. [ January 08, 2006: Message edited by: Paul Clapham ]

George Lin
Ranch Hand

Joined: Jan 11, 2005
Posts: 125

posted

0

Steve,

Originally posted by Steve Fahlbusch: George,

there are many ways of accomplishing this and since this is not a real problem (ie: this is a made-up homework assignment) why don't you post the full requirements, that way we can address you solution to the problem statement.

For instance, if this is for a data structures course the approach might be much differnt than an algorithms course. (and my previous posts reflected an approach i would expect from my students, but lets see what is expected).

It is not from a homework. The whole requirements are too long -- so I just post a spcific requirement independent part. The total goal is to do some matrix computation with very very limited storage -- for an embedded system. The time to do the computation is not a mandatory requirement -- only the additional space required needs to be limited to a minimal level.

Anyway, do you have any good ideas?

regards, George

George Lin
Ranch Hand

Joined: Jan 11, 2005
Posts: 125

posted

0

Charles,

Originally posted by Charles Lyons: My apologies - mostly the talk is about time complexity because memory is so cheap these days, so naturally I assumed this was your intention!

Now, I'm a little rusty on complexities, so please say if I'm talking rubbish. O(1) space complexity means the algorithm uses the same amount of storage memory space regardless of how large the input is.

I'm going to assume you're using a 2-dimensional array to store the data, and since that array could be of any datatype, I'll call it "Arr[][]". I'll let the first dimension be the rows, and the second the columns within each row. For an m x n matrix we therefore have Arr[m][n]. Clearly this array will have to be as large the matrix, and therefore will occupy more memory space for larger input - but this isn't the fault of the algorithm (only the input).

To be honest, I can't see a way to transpose a general m x n matrix without having a second Arr[n][m] array to put it in. We cannot dereference the first array to resize it, then reference its entries! We would have to have two arrays in memory.

However, we can optimise for a square n x n array with data Arr[n][n], since they we don't have to change the sizes of each dimension. We can create an O(1) space algorithm by swapping entries on either side of the principle diagonal, and I think this sketch should do it:

I think that should give O(1) space complexity - we are only declaring i, j and swap for each iteration, and these will always be declared for any size array. In addition, we only have swap for those entries above the diagonal, which is significantly less than half the matrix - for an n x n this is actually n*(n-1)/2.

The time complexity of this algorithm is O(n^2), making it inefficient. As I said previously, there are O(log[n]) algorithms, but they use caching of pieces of the matrix for efficiency, and this increases the space complexity. I would think this trade-off is probably worthwhile in the long-run.

I'm not so sure about the general m x n problem - please repost if you can clarify or have any further ideas...

I have found a solution to deal with the general m*n problem, please reference to "ACM Algorithm 467: Matrix Transposition in Place".

Anyway, I am very interested in the O(log[n]) time complexity algorithms, do you know where can I find related resources?

I would still set a flag, and swap the indices in all of the accessors.

Size complexity ( 1 bit - boolean value )

Time complexity O(1)

- so as i said earlier, change the accesors to check the flag and all setters/getters using swapped indicies [ January 09, 2006: Message edited by: Steve Fahlbusch ]

George Lin
Ranch Hand

Joined: Jan 11, 2005
Posts: 125

posted

0

Steve,

Originally posted by Steve Fahlbusch: George,

I would still set a flag, and swap the indices in all of the accessors.

Size complexity ( 1 bit - boolean value )

Time complexity O(1)

- so as i said earlier, change the accesors to check the flag and all setters/getters using swapped indicies

[ January 09, 2006: Message edited by: Steve Fahlbusch ]

In my question, I mean the space complexity -- not the time complexity -- to be O(1).

Anyway, I do not quite understand your points. Could you provide some pseudo-code please?

I know you mean size - look at my last post size complexity is 1 bit (not order of 1, but just 1 bit) - or normally stated - to implement a transpose that has a flag (boolean) and then changing all accessors to swap indicies if transposed (see earlier post) then the overhead would be one bit. In java this usually means throwing away a whole boolean, which is almost always smaller than one element of a matrix (one would expect say a double, or at least a float).

As to the pseudocode - that was provided for you in a previous post (for the getElement) you just need to implment that approach for any / all direct accessors of the underlying data (whatever that would be, you didn't specify). Normally this would only be two getElement and setElement. I would probably suggest a dynamic single indexed array - but that's up to you, and i couldn't recommend anything without seeing the requirements (as that will probably impact the implementation).

Originally posted by Jeff Verdegan: George, I helped you in Sun's forums. That's the last time I help you here or there. You should know better than to crosspost by now.

Whoa down there, pardner. Not everyone reads the Sun forums (I don't -- I find the people there to generally be too acerbic for my liking) and not everybody reads JavaRanch (fools!), so George was just trying to get the most amount of exposure to his problem. You certainly didn't have to answer him here (or there).

We do have a crossposting policy at JavaRanch -- choose one forum on the Ranch in which to ask your question. But we don't discourage people from posting the same question to multiple sites.

That said, I'm reading this and thiking that this is not really beginner's stuff anyway, so I'm going to move this to the intermediate forum. Please continue the discussion (nicely) there.

Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.