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

rotacion con matrices en java

Question

Posible duplicado:
Algoritmo para girar una imagen 90 grados en su lugar? (Sin memoria extra)

Al decir 90 grados quiero decir si:

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

luego después de la rotación de 90 grados A se convierte en:

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

Answer 1

El algoritmo es rotar cada "anillo", trabajando desde el más externo al más interno.

AAAAA
ABBBA
ABCBA
ABBBA
AAAAA

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

El índice i oscila entre 0..ring-width-1, por ejemplo, para A, el ancho es 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 para cada anillo interior sucesivo, compensando las coordenadas reduciendo el ancho del anillo en 2.

[Otra respuesta apareció con el código, así que no voy a repetir eso.]

Answer 2

Implementación completa en C utilizando el método descrito por @Narek anterior

#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 3

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, puede consultar aquí: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Answer 4

Necesitas una variable de temperatura, entonces solo es 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 5

Transponer e intercambiar filas o columnas (depende de si desea rotar hacia la izquierda o hacia la derecha).

p.ej

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 6

Ver este artículo para la transposición de matriz en el lugar; 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 .

Answer 7

dejar que a sea ​​una matriz nxn 0 indexación 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 la temperatura, esto funciona (también gira en la dirección correcta) esta vez en 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]

Nota: Esto solo funciona para matrices de enteros.