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

Duplication possible:
Algorithme pour faire pivoter une image de 90 degrés en 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 90 degrés de rotation A devient:

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

laisser a être un tableau nxn 0 indexation basée

 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 Si vous voulez éviter d’utiliser temp, cela fonctionne (il tourne également 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] 

Remarque: Ceci ne fonctionne que pour les masortingces d’entiers.

Transposer et échanger des lignes ou des colonnes (selon que vous souhaitez effectuer une rotation vers la gauche ou vers la droite).

par exemple

 1) original masortingx 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 atsortingbuer de mémoire.

L’algorithme consiste à faire pivoter chaque “anneau”, en travaillant de l’extérieur vers l’intérieur.

 AAAAA ABBBA ABCBA ABBBA AAAAA 

L’algorithme ferait tourner tous les A d’abord, puis B’s puis C. La rotation d’un anneau nécessite de déplacer 4 valeurs à la fois.

L’indice i est compris entre 0..ring-width-1, par exemple pour A la largeur est 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) 

Ceci est répété pour chaque anneau intérieur successif, en décalant les coordonnées réduisant la largeur de l’anneau de 2.

[Une autre réponse est apparue avec le code, alors je ne le répéterai pas.]

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

 #include  int n; unsigned int arr[100][100]; void rotate() { int i,j,temp; for(i=0; i 

Voir cet article pour la transposition de la masortingce en place; google également pour “transposition de masortingce sur place”. Il peut être facilement adapté pour effectuer une rotation de 90 degrés. Pour transposer des masortingces carrées, il suffit d’échanger b[i][j] avec b[j][i]b[k][l] est a[n*k+l] . Sur les masortingces non carrées, c’est beaucoup plus difficile. “Sans espace supplémentaire” est une exigence plutôt forte, peut-être que vous vouliez dire un espace O (1)? (en supposant que les entiers sont de taille fixe) Implémentation en C ++: ici .

Vous avez besoin d’une variable temporaire, alors il suffit de sauter des éléments.

 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; 

Je suis tombé sur la mise en œuvre suivante:

Pour les masortingces carrées:

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

Pour les masortingces rectangulars:

 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 

Pour plus d’informations, on peut se référer ici: http://en.wikipedia.org/wiki/In-place_masortingx_transposition