How to transpose a matrix?

[George2]

Hello everyone,

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

thanks in advance,
George

[jwenting]

Unless the matrix is square you won't be able to handle that, as arrays are immutable in size.

| 1 2 3 |
| 4 5 6 |
== [[1,2,3],[4,5,6]]

Can't be put in the same array as

| 1 4 |
| 2 5 |
| 3 6 |
== [[1,4],[2,5],[3,6]]

You're going to need some temporary storage anyway if you could get away with it (which you can with square matrices).
dest[i,j] = org[j,i] For each i,j;
Therefore you're going to have to store the value you're replacing until you've a place to put it (which is easy as you can quite readily figure out as you're effectively swapping valued in that scenario).

[George2]

jwenting,

Unless the matrix is square you won't be able to handle that, as arrays are immutable in size.

| 1 2 3 |
| 4 5 6 |
== [[1,2,3],[4,5,6]]

Can't be put in the same array as

| 1 4 |
| 2 5 |
| 3 6 |
== [[1,4],[2,5],[3,6]]

You're going to need some temporary storage anyway if you could get away with it (which you can with square matrices). dest[i,j] = org[j,i] For each i,j; Therefore you're going to have to store the value you're replacing until you've a place to put it (which is easy as you can quite readily figure out as you're effectively swapping valued in that scenario).

I think it is possible to represent a matrix by a linear array -- in that way, I think we can handle that. Do you agree?

Anyway, if you agree with that, do you have any ideas?

regards,
George

[iamthwee]

I think it is possible to represent a matrix by a linear array

If by linear u mean a 1 dimensional array, then yes thats possible. But to do so would B just stupid...

By convention matrices should be defined using two dimensions, row and column, this actually makes it easier to manipulate matrices :rolleyes:

And there are literally hundreds examples of matrix demos out there. Just try searching 4 'matrix.java' and c wat u get.

And wat's with the 20 questions? Don't no about u but I'm perplexed...

:?:

[George2]

iamthwee,

If by linear u mean a 1 dimensional array, then yes thats possible. But to do so would B just stupid...

It is meaningful. It can save space (foot print) if we represent a matrix using one dimensional array and we need to transpose the matrix frequently.

Anyway, do you have any ideas?

regards,
George

[jwenting]

no, you don't save a byte using a one dimensional array instead of a multidimensional array.

[George2]

jwenting,

no, you don't save a byte using a one dimensional array instead of a multidimensional array.

Why? I think any array (no matter of how much dimension it has) can be represented as one dimensional (linear) array. For example, we can create a method called element (i, j) to return the required element in a 2 dimensional array.

regards,
George

[jwenting]

yes you can, but the 1 dimensional array would take up the same amount of space in memory as would the 2 dimensional array.

And that's without the added address space needed for the accessfunctions (and the slower access to the data using those functions instead of whatever optimisations the JVM may employ on arrays).

[George2]

jwenting,

And that's without the added address space needed for the accessfunctions (and the slower access to the data using those functions instead of whatever optimisations the JVM may employ on arrays).

Could you please provide more detailed descriptions of the above points? For example, "the added address space needed for the accessfunctions" and "optimisations the JVM may employ on arrays" please?

regards,
George

[jwenting]

A method takes up space in memory.
A method call takes time in access to the instructions performed in that method.
The compiler may be able to optimise some instructions (like direct array access), making them a lot faster than doing the same through a method.

[George2]

jwenting,

A method takes up space in memory. A method call takes time in access to the instructions performed in that method. The compiler may be able to optimise some instructions (like direct array access), making them a lot faster than doing the same through a method.

It is only high level general perspective. I am wondering what do you mean in details.

Anyway, let us come beck to the original question, no matter using 1 dimensional array or using 2 dimensional array, do you have any idea of an implementation which takes only constant additional space complexity O(1).

regards,
George

[jwenting]

Whichever, you will need to define an array to hold the result.
That's going to take up the same space as the original array (it contains the same number of elements after all).
After that it's a linear operation putting element [i,j] of the original array into element [j,i] of the resulting array.
A simple nested for loop will do that.