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

6 Years
Discussion Span
Last Post by 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...} ?


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


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.


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?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.