How is it possible to transpose a MxN matrix without using a “buffering” matrix?
In the latter case it’s easy and quite the “classic” approach…
Given a matrix[M][N], I would like to put it into a void transpose_matrix(int matrix[][]) function which operates directly on the matrix passed as reference which, as previosly said, would edit the matrix memory space to transpose its elements.
e.g:
A =
1 2 3 4
5 6 7 8
9 1 2 3
A after transposing itself (without pretty printing)[1]:
1 5 9 2
6 1 3 7
2 4 8 3
How would A looked like in a NxM matrix:
1 5 9
2 6 1
3 7 2
4 8 3
Thanks!
[1]: Printing the matrix as if it was actually a “new” NxM matrix.
2
Doing that efficiently is complex.
Wikipedia has a nice article on the subject: In-place matrix transposition with many interesting references.
A simple “follow-the-cycles” C implementation with O(1) auxiliary storage requirement (and heavily non-consecutive memory accesses) is:
/// param[in] m input matrix
/// param[in] h number of rows of a m
/// param[in] w number of columns of a m
///
/// Performs in-place transposition of matrix a m.
void transpose(double m[], const unsigned h, const unsigned w)
{
for (unsigned start = 0; start <= w * h - 1; ++start)
{
unsigned next = start;
unsigned i = 0;
do
{
++i;
next = (next % h) * w + next / h;
} while (next > start);
if (next >= start && i != 1)
{
const double tmp = m[start];
next = start;
do
{
i = (next % h) * w + next / h;
m[next] = (i == start) ? tmp : m[i];
next = i;
} while (next > start);
}
}
}
You can find a faster (C++) implementation requiring O(MN) auxiliary storage, one bit per element, here (the In-place transposition of a matrix question on Stackoverflow). Also take a look at Transpose a 1 dimensional array, that does not represent a square, in place.
PS in a number of circumstances it isn’t necessary or desirable to physically reorder a matrix to its transposed ordering: it could be enough to provide options to specify that certain matrices are to be interpreted in transposed order.
Some details about the above algorithm (assuming the input matrix A(3;4) of your question):
The first chunk: (do … while) is a sort of sequence generator:
next-sequence start next i
-----------------------------------
[0] 0 0 1
[1,4,5,9,3] 1 1 5 <-
[2,8,10,7,6] 2 2 5 <-
[3,1] 3 1 1
[4,5,9,3] 4 3 3
[5,9,3] 5 3 2
[6,2] 6 2 1
[7,6] 7 6 1
[8,10,7] 8 7 2
[9,3] 9 3 1
[10,7] 10 7 1
[11] 11 11 1
Not every sequence is useful:
- sequences of length 1 (
i == 1e.g.[0]and[11]) mean no data motion and can be skipped; - sequences where the final value of
nextis smaller thanstartcan be skipped since they are sub-sequences of an already seen sequence.
Second chunk (if) will perform the data motion described by a sequence.
E.g. [1,4,5,9,3] means the value in position 4 goes to position 1, value in position 5 goes to position 4 … while position 1 goes to position 3 (written using the standard notation for cycles/permutations it’s (1 3 9 5 4)).
About the expression:
(position % h) * w + position / h;
this is a way to convert the position between the original and the transposed matrix.
3