How to rotate a matrix 90 degrees without using any extra space? [duplicate]

This question already has answers here: 开发者_如何学Go Closed 10 years ago.

Possible Duplicate:

Algorithm to rotate an image 90 degrees in place? (No extra memory)

By saying 90 degrees i mean to say if:

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

then after 90 degree rotation A becomes:

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

---

Transpose and interchange rows or columns (depends 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 done without allocating memory.

---

let a be an nxn array 0 based indexing

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

Edit If you want to avoid using temp, this works (it also rotates in the correct 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 matrices of integers.

---

The algorithm is to rotate each "ring", working from the outermost to the innermost.

AAAAA
ABBBA
ABCBA
ABBBA
AAAAA

The algorithm would rotate all the A's first, then B's then C's. Rotating a ring requires moving 4 values at once.

The index i ranges from 0..ring-width-1, e.g. for A the width is 5.

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

This is then repeated for each successive inner ring, offsetting the co-ordinates reducing the ring width by 2.

[Another answer has appeared with the code, so I'll not repeat that.]

---

Complete 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;
}

---

See this article for in-place matrix transposition; also google for "in-place matrix transposition". It can be easily adapted to perform rotation by 90 degrees. To transpose square matrices, you just interchange b[i][j] with b[j][i] where b[k][l] is a[n*k+l]. On nonsquare matrices, it's considerably more difficult. "Without any extra space" is a rather strong requirement, maybe you meant O(1) space? (assuming integers are fixed size) Implementation in C++: here.

---

You need one temp variable, then it is just to jump 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;

---

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 info, one can refer here: http://en.wikipedia.org/wiki/In-place_matrix_transposition