Transpose a matrix without a buffering one

Question

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.

Answer 1

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 == 1 e.g. [0] and [11]) mean no data motion and can be skipped;
• sequences where the final value of next is smaller than start can 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.