¿Cómo rotar una matriz 90 grados sin usar ningún espacio extra?

Question

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

Al decir 90 grados que quiero decir si: la rotación

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

a continuación, después de 90 grados A se convierte en:

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

Answer 1

Let a sea una indización de matriz de nxn 0 basada

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 

Editar Si desea evitar el uso de temperatura, esto funciona (que también gira en la dirección correcta) esta vez en pitón.

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] 

Nota: Esto solo funciona para matrices de enteros.

Answer 2

Necesita una variable de temperatura, luego solo para saltar los elementos.

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 3

Transpose e intercambie filas o columnas (depende de si desea girar hacia la izquierda o hacia la derecha).

e. gramo.

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 

Todas estas operaciones se pueden realizar sin asignar memoria.

Answer 4

El algoritmo consiste en girar cada "anillo", trabajando desde el más externo al más interno.

AAAAA 
ABBBA 
ABCBA 
ABBBA 
AAAAA 

El algoritmo rotaría todas las A primero, luego B y luego las C. Girar un anillo requiere mover 4 valores a la vez.

El índice i oscila entre 0..ring-width-1, p. Ej. para A el ancho es de 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) 

Esto se repite entonces para cada anillo interior sucesiva, compensando las coordenadas reduciendo la anchura del anillo por 2.

[Otra respuesta ha aparecido con el código, por lo No voy a repetir eso.]

Answer 5

me encontré con la siguiente implementación:

Para matrices cuadradas:

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

Para matrices rectangulares:

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 

Para obtener más información, se puede consultar aquí: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Answer 6

Ver this article para la transposición de matrices in situ ; también google para "transposición de matriz en el lugar". Se puede adaptar fácilmente para realizar una rotación de 90 grados. Para transponer matrices cuadradas, simplemente intercambie b[i][j] con b[j][i] donde b[k][l] es a[n*k+l]. En matrices no cuadradas, es considerablemente más difícil. "Sin ningún espacio extra" es un requisito bastante fuerte, ¿tal vez quisiste decir O (1) espacio? (suponiendo que los enteros sean de tamaño fijo) Implementación en C++: here.

aplicación

Answer 7

completa en C usando el método descrito por @Narek anteriormente

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