Transpose a 1-dimensional array that is not a square in place

Question

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

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

If the width is 4 and the 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 to:

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

I know how to do this by creating a new array, but I would like to know how to do this in place, as a solution to the previously mentioned question .

Answer 1

One way to do this is to transfer each existing element of the original matrix to a new position, trying first to pick up the value in the destination pointer so that it can also be moved to a new position. For an arbitrary NxM matrix, the destination index of an element in index X can be calculated as:

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

where the operator "/" represents integer division (factor), and "%" is the modulo operator (remainder). Here I use Python syntax.

The problem is that you are not guaranteed to intersect all the elements in your matrix if you start at any place. The easiest way to get around this is to save a bitmap image of elements that have been moved to the correct positions.

Here is the 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 sacrificed some optimizations for clarity here. More sophisticated algorithms can be used to avoid a bitmap - see the links in the corresponding Wikipedia article if you are really serious about saving memory by computing.

Answer 2

An easy way to transpose in place is to rotate each element in place, starting from the back of the matrix. You only need to rotate one element in place, so for 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 simply shows the elements rotated to their final position at each step.)

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

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

Or, a little better in a structured way:

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

Rotating 1 element is effectively non-ops, but 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); } } }