How to rotate the matrix 90 degrees without using additional space?

Question

Possible duplicate:
Algorithm to rotate the image 90 degrees? (No extra memory)

Speaking 90 degrees, I want to say if:

A = {1,2,3, 4,5,6, 7,8,9} 

then after 90 degrees the rotation of A becomes:

 A = {7,4,1, 8,5,2, 9,6,3} 

Answer 1

let a be nxn 0 based indexing based

 f = floor(n/2) c = ceil(n/2) for x = 0 to f - 1 for y = 0 to c - 1 temp = a[x,y] a[x,y] = a[y,n-1-x] a[y,n-1-x] = a[n-1-x,n-1-y] a[n-1-x,n-1-y] = a[n-1-y,x] a[n-1-y,x] = temp 

Change If you want to avoid using temp, this works (it also rotates in the right direction) this time in python.

 def rot2(a): n = len(a) c = (n+1) / 2 f = n / 2 for x in range(c): for y in range(f): a[x][y] = a[x][y] ^ a[n-1-y][x] a[n-1-y][x] = a[x][y] ^ a[n-1-y][x] a[x][y] = a[x][y] ^ a[n-1-y][x] a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y] a[n-1-x][n-1-y] = a[n-1-y][x] ^ a[n-1-x][n-1-y] a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y] a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x] a[y][n-1-x] = a[n-1-x][n-1-y]^a[y][n-1-x] a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x] 

Note. This only works for integer matrices.

Answer 2

Transpose and exchange rows or columns (depends on whether you want to rotate left or right).

e. g.

 1) original matrix 1 2 3 4 5 6 7 8 9 2) transpose 1 4 7 2 5 8 3 6 9 3-a) change rows to rotate left 3 6 9 2 5 8 1 4 7 3-b) or change columns to rotate right 7 4 1 8 5 2 9 6 3 

All these operations can be performed without memory allocation.

Answer 3

The algorithm is to rotate each “ring”, working from the external to the most internal.

 AAAAA ABBBA ABCBA ABBBA AAAAA 

The algorithm will rotate all A first, then B, and then C. To rotate the ring, you must immediately move 4 values.

Index i ranges from 0..ring-width-1, for example. for A, the width is 5.

  (i,0) -> temp (0, Ni-1) -> (i, 0) (Ni-1, N-1) -> (0, Ni-1) (N-1, i) -> (Ni-1, N-1) temp -> (N-1, i) 

Then this is repeated for each subsequent inner ring, compensating for the coordinates, reducing the width of the ring by 2.

[Another answer came up with code, so I won’t repeat it.]

Answer 4

See this article for transposition in place; also google for "transpose in place matrix". It can be easily adapted to rotate 90 degrees. To transpose square matrices, you simply change b[i][j] to b[j][i] , where b[k][l] is a[n*k+l] . On non-damped matrices it is much more complicated. “Without extra space” is a pretty strong requirement, maybe you meant O (1) space? (assuming integers are fixed size) C ++ implementation: here .

Answer 5

Full implementation in C using the method described by @Narek above

 #include <stdio.h> int n; unsigned int arr[100][100]; void rotate() { int i,j,temp; for(i=0; i<n; i++) { for(j=i; j<n; j++) { if(i!=j) { arr[i][j]^=arr[j][i]; arr[j][i]^=arr[i][j]; arr[i][j]^=arr[j][i]; } } } for(i=0; i<n/2; i++) { for(j=0; j<n; j++) { arr[j][i]^=arr[j][n-1-i]; arr[j][n-1-i]^=arr[j][i]; arr[j][i]^=arr[j][n-1-i]; } } } void display(){ int i,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) { printf("%d",arr[i][j]);} printf("%s","\n"); } } int main(int argc, char *argv[]){ int i,j; printf("%s","Enter size of matrix:"); scanf("%d",&n); printf("%s","Enter matrix elements\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&arr[i][j]); } } rotate(); display(); return 0; } 

Answer 6

You need one temporary variable, then you just need to move the elements around.

 temp = A[0]; A[0] = A[6]; A[6] = A[8]; A[8] = A[2]; A[2] = temp; temp = A[1]; A[1] = A[3]; A[3] = A[7]; A[7] = A[5]; A[5] = temp; 

Answer 7

I came across the following implementation:

For square matrices:

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

For rectangular matrices:

 for each length>1 cycle C of the permutation pick a starting address s in C let D = data at s let x = predecessor of s in the cycle while x ≠ s move data from x to successor of x let x = predecessor of x move data from D to successor of s 

For more information, please contact here: http://en.wikipedia.org/wiki/In-place_matrix_transposition