Faire pivoter un tableau 2D sur place sans utiliser un nouveau tableau - la meilleure solution C++?

Question

Un de mes élèves m'a demandé ce genre de devoir avec des tableaux C++. Cela m'a semblé très intéressant, alors même si j'ai résolu ce problème, je voulais partager ma solution avec vous et connaître d'autres variantes et opinions. Le problème est le suivant:

problème lui est attribuée une matrice quadratique 2D dynamique (tableau) A (nxn). Il est nécessaire de faire pivoter la matrice de 90 degrés dans le sens inverse des aiguilles d'une montre, c'est-à-dire qu'après la rotation, le champ A [1,1] doit contenir la valeur de A [1, n] et le champ A [1, n] A [n, n]. Et il est également nécessaire que tout en résolvant ce problème, vous ne devez utiliser aucun autre tableau.

Ma solution Je vous ai dit à l'étudiant de faire ce qui suit (étapes représentera schématiquement):
je l'ai suggéré de définir une classe qui, comme son membre, aura le tableau 2D. Et de définir une opération qui référence le retour sur A [j, n + 1-i] élément lorsque l'utilisateur demandera A [i, j] une. En deux mots, je l'ai suggéré de créer une enveloppe pour le tableau, et manipuler par réseau à travers l'emballage.

Answer 1

Wikipédia a un article sur in-place matrix transposition.

Tenir compte:

a b c 
e f g 
x y z 

transpose: 
a e x 
b f y 
c g z 

rotated 90 deg CCW: 
c g z 
b f y 
a e x 

Donc une fois que vous avez la transposition, inverser les lignes, que vous pouvez faire en place facilement.

Answer 2

Vous pouvez utiliser un "quatre voies-échange" et une boucle imbriquée avec la magie de rotation (travaillé sur papier):

template <typename T> 
void swap(T& a, T& b, T& c, T& d) 
{ 
    T x(a); 
    a = b; 
    b = c; 
    c = d; 
    d = x; 
} 

template <typename T, size_t dim> 
void rotate(T (&matrix)[dim][dim]) 
{ 
    const size_t d = dim-1; 
    for (size_t y = 0; y < dim/2; ++y) 
    { 
     for (size_t x = y; x < d-y; ++x) 
     { 
      swap(matrix[y ][x ], 
       matrix[x ][d-y], 
       matrix[d-y][d-x], 
       matrix[d-x][y ]); 
     } 
    } 
} 

Programme de test:

template <typename T, size_t dim> 
void print(T (&matrix)[dim][dim]) 
{ 
    for (size_t y = 0; y < dim; ++y) 
    { 
     for (size_t x = 0; x < dim; ++x) 
     { 
      std::cout << matrix[y][x] << ' '; 
     } 
     std::cout << '\n'; 
    } 
} 

int main() 
{ 
    int matrix[4][4] = {{1, 2, 3, 4}, 
         {5, 6, 7, 8}, 
         {9, 10, 11, 12}, 
         {13, 14, 15, 16}}; 
    rotate(matrix); 
    print(matrix); 
} 

Sortie:

4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13 

maintenant, il vous suffit de le convertir à partir du modèle de forme à forme dynamique;)

Answer 3

Eh bien, ce n'est pas C++ mais Java. Désolé pour cela, mais voici un algorithme récursif dans un simple tableau soutenu Matrix:

public void rotateInPlaceRecursive() { 
    if(rowCount != colCount) { 
     throw new IllegalStateException("Matrix must be square"); 
    } 
    doRotateInPlaceRecursive(0); 
} 

public void doRotateInPlaceRecursive(int shrink) { 
    if(shrink == rowCount/2) { 
     return; 
    } 
    for (int col = shrink; col < colCount-shrink-1; col++) { 
     int row = shrink; 
     int top  = tab[row][col]; 
     int left = tab[rowCount-col-1][row]; 
     int bottom = tab[rowCount-row-1][rowCount-col-1]; 
     int right = tab[col][rowCount-row-1]; 

     tab[row][col] = right; 
     tab[rowCount-col-1][row] = top; 
     tab[rowCount-row-1][rowCount-col-1] = left; 
     tab[col][rowCount-row-1] = bottom; 

    } 
    doRotateInPlaceRecursive(shrink+1); 
} 

---- ESSAI

@Test 
public void testRotateInPlaceRecursive() { 
    // given 
    int N = 5; 
    Matrix matrix = new Matrix(N, N); 

    // when 
    int i=0; 
    for(int row = 0; row< N; row++) { 
     for(int col = 0; col< N; col++) { 
      matrix.set(row,col, i++); 
     } 
    } 

    // then 
    matrix.rotateInPlaceRecursive(); 
    i = 0; 
    for(int row = 0; row< N; row++) { 
     for(int col = 0; col< N; col++) { 
      assertEquals(i++,matrix.get(N-col-1,row)); 
     } 
    } 
} 

Answer 4

O (n^2) temps et O (1) algorithme spatial (sans solutions de contournement et des trucs entourloupettes!)

Rotation de 90:

Transpose 
Reverse each row 

Rotation de -90:

Transpose 
Reverse each column 

Rotation de 180:

Méthode 1: Faire tourner par deux fois 90

Méthode 2: Inverser chaque ligne, puis inverser chaque colonne

Rotation de -180:

Méthode 1: Rotation de -90 deux fois

Méthode 2: Reverse chaque colonne, puis inverser chaque ligne

Méthode 3: inverse par 180 car ils sont même

Answer 5

L'exemple ci-dessous est en Java et peut être facilement adopté en C++. La rotation de grandes matrices en mémoire peut consommer beaucoup de ressources, en particulier lorsque les valeurs de la matrice sont des objets complexes. Dans de tels cas, il pourrait être plus efficace de recalculer les index avec des fonctions qui les redirigeraient vers des éléments de matrice pivotée sans rotation réelle.

public class RotateArray { 

public static char arr[][] = { { 'a', 'b', 'c','1' }, { 'd', 'e', 'f','2' }, { 'g', 'h', 'i','3' },{ 'j', 'k', 'l','4' } }; 
private static int imax = arr.length-1; 
private static int jmax = arr[0].length-1; 

public static void printArray() { 

    for (int i = 0; i <= imax; i++) { 
     for (int j = 0; j <= jmax; j++) { 
      System.out.print(arr[i][j] + " "); 
     } 
     System.out.print("\n"); 
    } 
} 

public static void printRotatedArray() { 
    for (int i = 0; i <= imax; i++) { 
     for (int j = 0; j <= jmax; j++) { 
      System.out.print(arr[getRotatedI(i,j)][getRotatedJ(i,j)] + " "); 
     } 
     System.out.print("\n"); 
    } 
} 

public static int getRotatedI(int i,int j){  
    int ii = imax-j; 
    return ii; 
} 

public static int getRotatedJ(int i,int j){ 
    int jj = i; 
    return jj; 
}  

public static void main(String[] args) { 

    System.out.println("Printing matrix"); 
    printArray(); 
    System.out.println("Printing rotated matrix"); 
    printRotatedArray(); 
} 

} 

Sortie:

Printing matrix 
a b c 1 
d e f 2 
g h i 3 
j k l 4 

Printing rotated matrix 
j g d a 
k h e b 
l i f c 
4 3 2 1