Matrix Transpose

[onako]

I store matrix entries in std::vector<double>, such that the reading is row by row.
This means, for matrix
1 3 4 8 9 3
3 6 8 1 1 2
2 0 9 8 7 6

the std::vector<double> would have entries: {1,3,4,8,9,3,3,6,8,1,1,2,2,0,9,8,7,6}.
To transpose the matrix I use the naive approach of iterating through std::vector, calculating for each
entry its position in a matrix transpose. Recently, I got one suggestion:

"When you have a matrix and a mapping to a one-dimensional vector, transposing is equivalent to a permutation. Now execute this permutation by sorting the elements by requested rank in the permutation result."

I understand that transposing is equivalent to a permutation, but I dont know how to approach the problem this way.
Any suggestion on how to do this (or to do matrix transpose is a faster way) is welcome.
--- I understand it is C++ specific (according to the description), but it is general programming problem. Thanks

[jon.kiparsky]

Interesting question. My boss will be annoyed at you. :)

I think I understand the problem, but just to be clear, can you show me what the outcome of the transposition would be? I'm not a math guy, so I'm not sure I've got your terminoogy right.

Would it be:

2 3 1
0 6 3
...

and a vector {2, 3, 1, 0, 6, 3, 0, 8, 4...} ?

[onako]

Transposed matrix (row and columns substituted) would be
1 3 2
3 6 0
4 8 9
8 1 8
....
and the corresponding vector:{1,3,2,3,6,0,4,8,9,8,1,8...}

[jon.kiparsky]

Thanks. So the problem is to go from vector to vector? From
{1,3,4,8,9,3,3,6,8,...} to {1,3,2,3,6,0,4,8,9,8,1,8...} in an efficient manner?

I think I see your naive method - go from index in vector 1 to x,y coordinates in matrix 1, swap x and y values, and calculate index in vector, combining and simplifying those equations to do it as one calculation.

The permutation solution, though, is not obvious to me. Fortunately, I'm a contractor and will therefore be getting paid to think about this.

[onako]

Please share your solution. Thanks

[jon.kiparsky]

Haven't been able to come up with anything more clever than walking down the list of entries and transforming index i1 to i2:
i2 = (i1%cols)*rows + i/cols

That'll take the index in the original matrix (i1) and convert it to the index in the transposed matrix (i2)- I think that's what you were saying you were already doing.
I'm not sure about the other solution, though. Sorry - if there's a better way to do this, I'm not seeing it. Can you say more about this permutation?