Inplace M x N size matrix transpose | Updated - GeeksforGeeks

Inplace M x N size matrix transpose | Updated - GeeksforGeeks
Given an M x N matrix, transpose the matrix without auxiliary memory.It is easy to transpose matrix using an auxiliary array. If the matrix is symmetric in size, we can transpose the matrix inplace by mirroring the 2D array across it's diagonal (try yourself). How to transpose an arbitrary size matrix inplace? See the following matrix,

// Non-square matrix transpose of matrix of size r x c and base address A

void MatrixInplaceTranspose(int *A, int r, int c)

{

    int size = r*c - 1;

    int t; // holds element to be replaced, eventually becomes next element to move

    int next; // location of 't' to be moved

    int cycleBegin; // holds start of cycle

    int i; // iterator

    bitset<HASH_SIZE> b; // hash to mark moved elements

    b.reset();

    b[0] = b[size] = 1;

    i = 1; // Note that A[0] and A[size-1] won't move

    while (i < size)

    {

        cycleBegin = i;

        t = A[i];

        do

        {

            // Input matrix [r x c]

            // Output matrix 1

            // i_new = (i*r)%(N-1)

            next = (i*r)%size;

            swap(A[next], t);

            b[i] = 1;

            i = next;

        }

        while (i != cycleBegin);

        // Get Next Move (what about querying random location?)

        for (i = 1; i < size && b[i]; i++)

            ;

        cout << endl;

    }

}

Some readers identified similarity between the matrix transpose and string transformation. Without much theory I am presenting the problem and solution. In given array of elements like [a1b2c3d4e5f6g7h8i9j1k2l3m4]. Convert it to [abcdefghijklm1234567891234]. The program should run inplace. 

void MatrixTransposeInplaceArrangement(data_t A[], int r, int c) {

   int size = r*c - 1;

   data_t t; // holds element to be replaced, eventually becomes next element to move

   int next; // location of 't' to be moved

   int cycleBegin; // holds start of cycle

   int i; // iterator

   bitset<HASH_SIZE> b; // hash to mark moved elements

   b.reset();

   b[0] = b[size] = 1;

   i = 1; // Note that A[0] and A[size-1] won't move

   while( i < size ) {

      cycleBegin = i;

      t = A[i];

      do {

         // Input matrix [r x c]

         // Output matrix 1

         // i_new = (i*r)%size

         next = (i*r)%size;

         swap(A[next], t);

         b[i] = 1;

         i = next;

      } while( i != cycleBegin );

      // Get Next Move (what about querying random location?)

      for(i = 1; i < size && b[i]; i++)

         ;

      cout << endl;

   }

}

https://rosettacode.org/wiki/Matrix_transposition#Java

               double[][] ans = new double[m[0].length][m.length];
               for(int rows = 0; rows < m.length; rows++){
                       for(int cols = 0; cols < m[0].length; cols++){
                               ans[cols][rows] = m[rows][cols];
                       }
               }

http://introcs.cs.princeton.edu/java/14array/Transpose.java.html

        // transpose in-place
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                int temp = a[i][j];
                a[i][j] = a[j][i];
                a[j][i] = temp;
            }
        }

https://en.wikipedia.org/wiki/In-place_matrix_transposition
https://devblogs.nvidia.com/parallelforall/efficient-matrix-transpose-cuda-cc/
Read full article from Inplace M x N size matrix transpose | Updated - GeeksforGeeks