About four months of gap (missing GFG), a new post. 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,

a b c a d g j
d e f ==> b e h k
g h i c f i l
j k l

As per 2D numbering in C/C++, corresponding location mapping looks like,

Org element New
0 a 0
1 b 4
2 c 8
3 d 1
4 e 5
5 f 9
6 g 2
7 h 6
8 i 10
9 j 3
10 k 7
11 l 11

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

- 1->4->5->9->3->1 – Total 5 elements form the cycle
- 2->8->10->7->6->2 – Another 5 elements form the cycle
- 0 – Self cycle
- 11 – Self cycle

From the above example, we can easily devise an algorithm to move the elements along these cycles. *How can we generate permutation cycles?* Number of elements in both the matrices are constant, given by N = R * C, where R is row count and C is column count. An element at location *ol* (old location in R x C matrix), moved to *nl* (new location in C x R matrix). We need to establish relation between *ol, nl, R* and *C*. Assume *ol = A[or][oc]*. In C/C++ we can calculate the element address as,

ol = or x C + oc (ignore base reference for simplicity)

It is to be moved to new location *nl* in the transposed matrix, say *nl = A[nr][nc]*, or in C/C++ terms

nl = nr x R + nc (R - column count, C is row count as the matrix is transposed)

Observe, *nr = oc *and* nc = or*, so replacing these for *nl*,

nl = oc x R + or -----> [eq 1]

after solving for relation between *ol* and *nl*, we get

ol = or x C + oc
ol x R = or x C x R + oc x R
= or x N + oc x R (from the fact R * C = N)
= or x N + (nl - or) --- from [eq 1]
= or x (N-1) + nl

OR,

nl = ol x R - or x (N-1)

Note that the values of *nl* and *ol* never go beyond *N-1*, so considering modulo division on both the sides by (*N-1*), we get the following based on properties of congruence,

nl mod (N-1) = (ol x R - or x (N-1)) mod (N-1)
= (ol x R) mod (N-1) - or x (N-1) mod(N-1)
= ol x R mod (N-1), since second term evaluates to zero
nl = (ol x R) mod (N-1), since *nl* is always less than *N-1*

**A curious reader might have observed the significance of above relation. Every location is scaled by a factor of R (row size). It is obvious from the matrix that every location is displaced by scaled factor of R. The actual multiplier depends on congruence class of (N-1), i.e. the multiplier can be both -ve and +ve value of the congruent class.**Hence every location transformation is simple modulo division. These modulo divisions form cyclic permutations. We need some book keeping information to keep track of already moved elements. Here is code for inplace matrix transformation,

`#include <stdio.h>`

`#include <iostream>`

`#include <bitset>`

`#define HASH_SIZE 128`

`using`

`namespace`

`std;`

`void`

`Print2DArray(`

`int`

`*A, `

`int`

`nr, `

`int`

`nc)`

`{`

` `

`for`

`(`

`int`

`r = 0; r < nr; r++)`

` `

`{`

` `

`for`

`(`

`int`

`c = 0; c < nc; c++)`

` `

`printf`

`(`

`"%4d"`

`, *(A + r*nc + c));`

` `

`printf`

`(`

`"\n"`

`);`

` `

`}`

` `

`printf`

`(`

`"\n\n"`

`);`

`}`

`void`

`MatrixInplaceTranspose(`

`int`

`*A, `

`int`

`r, `

`int`

`c)`

`{`

` `

`int`

`size = r*c - 1;`

` `

`int`

`t; `

` `

`int`

`next; `

` `

`int`

`cycleBegin; `

` `

`int`

`i; `

` `

`bitset<HASH_SIZE> b; `

` `

`b.reset();`

` `

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

` `

`i = 1; `

` `

`while`

`(i < size)`

` `

`{`

` `

`cycleBegin = i;`

` `

`t = A[i];`

` `

`do`

` `

`{`

` `

` `

` `

` `

`next = (i*r)%size;`

` `

`swap(A[next], t);`

` `

`b[i] = 1;`

` `

`i = next;`

` `

`}`

` `

`while`

`(i != cycleBegin);`

` `

` `

`for`

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

` `

`;`

` `

`cout << endl;`

` `

`}`

`}`

`int`

`main(`

`void`

`)`

`{`

` `

`int`

`r = 5, c = 6;`

` `

`int`

`size = r*c;`

` `

`int`

`*A = `

`new`

`int`

`[size];`

` `

`for`

`(`

`int`

`i = 0; i < size; i++)`

` `

`A[i] = i+1;`

` `

`Print2DArray(A, r, c);`

` `

`MatrixInplaceTranspose(A, r, c);`

` `

`Print2DArray(A, c, r);`

` `

`delete`

`[] A;`

` `

`return`

`0;`

`}`

Output:

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
1 7 13 19 25
2 8 14 20 26
3 9 15 21 27
4 10 16 22 28
5 11 17 23 29
6 12 18 24 30

In given array of elements like [a1b2c3d4e5f6g7h8i9j1k2l3m4]. Convert it to [abcdefghijklm1234567891234]. The program should run inplace. What we need is an inplace transpose. Given below is code.

`#include <stdio.h>`

`#include <iostream>`

`#include <bitset>`

`#define HASH_SIZE 128`

`using`

`namespace`

`std;`

`typedef`

`char`

`data_t;`

`void`

`Print2DArray(`

`char`

`A[], `

`int`

`nr, `

`int`

`nc) {`

` `

`int`

`size = nr*nc;`

` `

`for`

`(`

`int`

`i = 0; i < size; i++)`

` `

`printf`

`(`

`"%4c"`

`, *(A + i));`

` `

`printf`

`(`

`"\n"`

`);`

`}`

`void`

`MatrixTransposeInplaceArrangement(data_t A[], `

`int`

`r, `

`int`

`c) {`

` `

`int`

`size = r*c - 1;`

` `

`data_t t; `

` `

`int`

`next; `

` `

`int`

`cycleBegin; `

` `

`int`

`i; `

` `

`bitset<HASH_SIZE> b; `

` `

`b.reset();`

` `

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

` `

`i = 1; `

` `

`while`

`( i < size ) {`

` `

`cycleBegin = i;`

` `

`t = A[i];`

` `

`do`

`{`

` `

` `

` `

` `

`next = (i*r)%size;`

` `

`swap(A[next], t);`

` `

`b[i] = 1;`

` `

`i = next;`

` `

`} `

`while`

`( i != cycleBegin );`

` `

` `

`for`

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

` `

`;`

` `

`cout << endl;`

` `

`}`

`}`

`void`

`Fill(data_t buf[], `

`int`

`size) {`

` `

` `

`for`

`(`

`int`

`i = 0; i < size; i++)`

` `

`buf[i] = `

`'a'`

`+i;`

` `

` `

`buf += size;`

` `

`for`

`(`

`int`

`i = 0; i < size; i++)`

` `

`buf[i] = `

`'0'`

`+i;`

`}`

`void`

`TestCase_01(`

`void`

`) {`

` `

`int`

`r = 2, c = 10;`

` `

`int`

`size = r*c;`

` `

`data_t *A = `

`new`

`data_t[size];`

` `

`Fill(A, c);`

` `

`Print2DArray(A, r, c), cout << endl;`

` `

`MatrixTransposeInplaceArrangement(A, r, c);`

` `

`Print2DArray(A, c, r), cout << endl;`

` `

`delete`

`[] A;`

`}`

`int`

`main() {`

` `

`TestCase_01();`

` `

`return`

`0;`

`}`

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org