Transpose of non-symmetric matrix

Given a M*N order matrix, which is stored in an array in a row-major order. eg. if the  matrix is of order 2*4 with below elements

a b c d
e f g h

Then it is stored in a one dimensional array as below:

a b c d e f g h

Write a program which will convert this matrix to its transpose.

Solution:

If the Matrix is symmetric (i.e number of rows & columns are equal), then calculating transpose is very easy. we just need to traverse the array and swap element at (i,j) position with element at (j,i) position.

The code is also quite simple:

#define M 4
#define N 4
void transpose(int arr[M][N])
{
    for(int i=0; i<M;i++)
    {
        for(int j=0; i<N; j++)
        {
            int temp = arr[i][j];
            arr[i][j] = arr[j][i];
            arr[j][i] = temp;
        }
    }
}

The problem comes when the 2-dim array is not symmetric. Because in that case if an element goes at position (i, j), then is not necessary that the other element will come at it position. Hence, swapping is not possible.

Like in the above example: element ‘c‘ is moving from position (0, 2) to (2, 0).. but the position (2,0) was not present in the original array.. and hence there is no element to swap from that position.

In fact in case of a-symmetric arrays, its the cycle of element which is shifted. Lets look at it more closely. The below table shows the old position and new position of all the element in matrix:

Note that the first and last elements stay in their original location. We can easily see the transformation forms new swapping cycles.

Element at 1 (b) moves to 2
Element at 2 (c) moves to 4
Element at 4 (e) moves to 1

Hence 1 -> 2 -> 4 -> 1 is one swap cycle

Another swap cycle is: 3 -> 6 -> 5 -> 3

And first and last element remains at their original positions. In case of any asymmetric matrix these cycles will be present (not the same order, but such cycles will be there). Now we have to move around the cycle. So we need to find a way to calculate the new position from the old position.

Hence New position (in one dim array) can be found from old position and old i value. We can further remove the dependency on oi (because we are only given a one dimensional array) take modulo (N-1) on both sides of above result:

np mod (N-1) = (op*m - oi * (N-1)) mod (N-1)
             = (op*m) mod (N-1) - (oi * (N-1) mod (N-1) )
      Now, (N-1) mod (N-1) = 0, Hence
np mod (N-1) = (op*m) mod (N-1)

Now since np is always < (N-1) .. there are only N elements in the array, and last element is never considered because it is already at its right position. Hence

np mod (N-1) = np

therefore

np =  (op*m) mod (N-1)

Now let’s write the code:

/** Function to calculate the transpose of Matrix.
 *  It calculate the new position using the following formula:
 *    np = (op * m) % (N-1)
 *
 *  Also keeps a hash to see which locations are already considered.
 */
void MatrixTranspose(int *arr, int m, int n)
{
    int N = m*n;
    int hash[m*n] = {false}; // false means - location not considered.
    hash[0] = hash[m*n-1] = 1; // 1st & last elements does'nt change position.
    // Since first element does not move. Hence first position to move is 1.
    int posToMove = 1;
    while (posToMove < N-1)
    {
        int startPos = posToMove;
        int value = arr[posToMove];
        // Loop iterate for one complete cycle
        do
        {
            int nextPos = (posToMove * m) % (N-1);
            // swap value & arr[nextPos]
            int temp = value;
            value = arr[nextPos];
            arr[nextPos] = temp;
            hash[posToMove] = true;
            posToMove = nextPos;
        }while (posToMove != startPos);
        // Finding the start position for next cycle
        for (posToMove = 1; posToMove < N-1 && hash[posToMove]; posToMove++)
            ;
    }
}

Note that this code uses variable length arrays A feature which was introduced in C99 but not implemented by many compilers. If your compiler gives warning at the below code:

    int hash[m*n] = {false}; // false means - location not considered.

Then define it as dynamic array

    int * hash = (int*) malloc(sizeof(int) *(m*n));
    for(int i=0; i<m*n; i++)
        hash[i] = false;

In this case, also remember to deallocate memory the end (before function terminates)

    free(hash);