Comment faire pivoter une matrice de 90 degrés sans utiliser d'espace supplémentaire ?

Question

Duplicata possible :
Algorithme pour faire pivoter une image de 90 degrés sur place ? (Pas de mémoire supplémentaire)

En disant 90 degrés, je veux dire si :

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

puis après une rotation de 90 degrés, A devient :

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

Answer 1

Transposez et interchangez les lignes ou les colonnes (selon que vous voulez faire une rotation à gauche ou à droite).

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

Toutes ces opérations peuvent être effectuées sans allouer de mémoire.

Answer 2

Let a être un tableau nxn indexation basée sur 0

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 vous voulez éviter d'utiliser temp, ceci fonctionne (il tourne aussi dans le bon sens) cette fois 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]

Note : Cela ne fonctionne que pour les matrices d'entiers.

Answer 3

L'algorithme consiste à faire tourner chaque "anneau", en allant du plus extérieur au plus intérieur.

AAAAA
ABBBA
ABCBA
ABBBA
AAAAA

L'algorithme ferait tourner d'abord tous les A, puis les B et enfin les C. Pour faire tourner un anneau, il faut déplacer 4 valeurs à la fois.

L'indice i est compris entre 0 et la largeur de l'anneau 1, par exemple, pour A, la largeur est 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)  

Cette opération est ensuite répétée pour chaque anneau intérieur successif, en décalant les coordonnées et en réduisant la largeur de l'anneau de 2.

(Une autre réponse est apparue avec le code, je ne la répéterai donc pas).

Answer 4

Ver cet article pour la transposition de la matrice en place ; recherchez également dans Google "transposition de la matrice en place". Il peut être facilement adapté pour effectuer une rotation de 90 degrés. Pour transposer des matrices carrées, il suffit d'interchanger b[i][j] con b[j][i] donde b[k][l] es a[n*k+l] . Pour les matrices non carrées, c'est beaucoup plus difficile. "Sans aucun espace supplémentaire" est une exigence plutôt forte, peut-être vouliez-vous dire O(1) espace ? (en supposant que les entiers sont de taille fixe) Implémentation en C++ : aquí .

Answer 5

Implémentation complète en C en utilisant la méthode décrite par @Narek ci-dessus

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