how to swap array-elements to transfer the array from a column-like into a row-like representation

Question

For example: the array

a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3

represents following table

a1, b1, c1, d1
a2, b2, c2, d2
a3, b3, c3, d3

now i like to bring the array into following form

a1, b1, c1, d1, a2, b2, c2, d2, a3, b3, c3, d3

Does an algorithm exist, which takes the array (from the first form) and the dimensions of the table as input arguments and which transfers the array into the second form? I thougt of an algorithm which doesn't need to allocate additional memory, instead i think it should be possible to do the job with element-swap operations.

Answer 1

The term you're looking for is in-place matrix transpose, and here's an implementation.

Answer 2

This is nothing more than an in-place matrix transposition. Some pseudo-code:

for n = 0 to N - 2
    for m = n + 1 to N - 1
        swap A(n,m) with A(m,n)

As you can see, you'll need 2 indices to access an element. This can be done by transforming (n,m) to nP+m with P being the number of columns.

Answer 3

Wikipedia devotes an article to this process, which is called In-place Matrix Transposition.

http://en.wikipedia.org/wiki/In-place_matrix_transposition

Answer 4

Why bother? If they are laid out in a 1-D array and you know how many elements there are in a logical row/span then you can get sequentially at any index with a little arithmetic.

int index(int row, int col, int elements)
{
  return ((row * elements) + col);
}

int inverted_index(int row, int col, int elements)
{
  return ((col * elements) + row);
}

then when you access the elements you can say something like...

array[index(row, col, elements)];
array[inverted_index(row, col, elements)];

I do most of my basic array manipulation like this for precisely the reason that I can transpose a matrix just by indexing it differently without any memory shuffling. It is also just about the fastest thing you can do with a computer.

You can follow the same principle and address your first array in terms that meet the needs of your final example with some of your own arithmetic.