Transpose a 1 dimensional array, that does not represent a square, in place

Question

This question is similar to this, but instead of an array that represents a square, I need to transpose a rectangular array.

So, given a width: x and a height: y, my array has x*y elements.

If width is 4 and height is 3, and I have:

{0,1,2,3,4,5,6,7,8,9,10,11}

which represents the matrix:

0 1 2  3
4 5 6  7
8 9 10 11

I would like:

{0,4,8,1,5,9,2,6,10,3,7,11}

I know how to do it by making a new array, but I'd like to know how to do it in place like the solution for the previously mentioned question.

Answer 1

A simple way to transpose in place is to rotate each element into place starting from the back of the matrix. You only need to rotate a single element into place at a time, so for the example, starting with [0,1,2,3,4,5,6,7,8,9,a,b], you get:

0,1,2,3,4,5,6,7,8,9,a,b, // step 0
                     ,b, // step 1
             ,8,9,a,7,   // step 2
      4,5,6,8,9,a,3,     // step 3
               ,a,       // step 4
         ,8,9,6,         // step 5
   ,4,5,8,9,2,           // step 6
         ,9,             // step 7
     ,8,5,               // step 8
 ,4,8,1,                 // step 9
   ,8,                   // step 10
 ,4,                     // step 11
0,                       // step 12

(This just shows the elements rotated into their final position on each step.)

If you write out how many elements to rotate for each element (from back to front), it forms a nice progression. For the example (width= 4, height= 3):

1,4,7,1,3,5,1,2,3,1,1,1

Or, in a slightly better structured way:

1,4,7,
1,3,5,
1,2,3,
1,1,1

Rotations of 1 element are effectively no-ops, but the progression leads to a very simple algorithm (in C++):

void transpose(int *matrix, int width, int height)
{
    int count= width*height;

    for (int x= 0; x<width; ++x)
    {
        int count_adjustment= width - x - 1;

        for (int y= 0, step= 1; y<height; ++y, step+= count_adjustment)
        {
            int last= count - (y+x*height);
            int first= last - step;

            std::rotate(matrix + first, matrix + first + 1, matrix + last);
        }
    }
}

Answer 2

One way to do this, is to move each existing element of the original matrix to its new position, taking care to pick up the value at the destination index first, so that it can also be moved to its new position. For an arbitrary NxM matrix, the destination index of an element at index X can be calculated as:

X_new = ((N*X) / (M*N)) + ((N*X) % (M*N))

where the "/" operator represents integer division (the quotient) and the "%" is the modulo operator (the remainder) -- I'm using Python syntax here.

The trouble is that you're not guaranteed to traverse all the elements in your matrix if you start at an arbitrary spot. The easiest way to work around this, is to maintain a bitmap of elements that have been moved to their correct positions.

Here's some Python code that achieves this:

M = 4
N = 3
MN = M*N

X = range(0,MN)

bitmap = (1<<0) + (1<<(MN-1))
i = 0

while bitmap != ( (1<<MN) - 1):
    if (bitmap & (1<<i)):
        i += 1
        xin = X[i]
        i = ((N*i)/MN) + ((N*i) % MN)
    else:
        xout = X[i]
        X[i] = xin
        bitmap += (1<<i)
        i = ((N*i)/MN) + ((N*i) % MN)
        xin = xout

print X

I've sacrificed some optimisation for clarity here. It is possible to use more complicated algorithms to avoid the bitmap -- have a look at the references in the related Wikipedia article if you're really serious about saving memory at the cost of computation.