Monday, March 21, 2016

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/