Comment faites-vous pivoter un tableau bidimensionnel?

Inspiré par le post de Raymond Chen , disons que vous avez un tableau bidimensionnel 4x4, écrivez une fonction qui le fait pivoter de 90 degrés. Raymond établit un lien vers une solution en pseudo-code, mais j'aimerais voir des trucs du monde réel.

[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]

Devient:

[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]

Mise à jour : la réponse de Nick est la plus simple, mais existe-t-il un moyen de le faire mieux que n ^ 2? Et si la matrice était de 10000x10000?

Le voici en C #

int[,] array = new int[4,4] {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,0,1,2 },
    { 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}

Algorithme de temps O (n ^ 2) et espace O (1) (sans solution de contournement ni truc de mordant!)

Rotation de +90:

1. Transposer
2. Inverser chaque ligne

Rotation de -90:

Méthode 1:

1. Transposer
2. Inverser chaque colonne

Méthode 2:

1. Inverser chaque ligne
2. Transposer

Rotation de +180:

Méthode 1 : rotation de +90 deux fois

Méthode 2 : inverser chaque ligne, puis inverser chaque colonne (transposer)

Rotation de -180:

Méthode 1 : rotation de -90 deux fois

Méthode 2 : inversez chaque colonne, puis inversez chaque ligne

Méthode 3 : rotation de +180 car ils sont identiques

Je voudrais ajouter un peu plus de détails. Dans cette réponse, les concepts clés sont répétés, le rythme est lent et intentionnellement répétitif. La solution proposée ici n'est pas la plus compacte syntaxiquement, elle est cependant destinée à ceux qui souhaitent savoir ce qu'est la rotation matricielle et l'implémentation qui en résulte.

Tout d'abord, qu'est-ce qu'une matrice? Aux fins de cette réponse, une matrice n'est qu'une grille dont la largeur et la hauteur sont identiques. Notez que la largeur et la hauteur d'une matrice peuvent être différentes, mais pour simplifier, ce didacticiel ne considère que les matrices de largeur et de hauteur égales ( matrices carrées ). Et oui, matrices est le pluriel de matrice.

Exemples de matrices: 2 × 2, 3 × 3 ou 5 × 5. Ou, plus généralement, N × N. Une matrice 2 × 2 aura 4 carrés car 2 × 2 = 4. Une matrice 5 × 5 aura 25 carrés car 5 × 5 = 25. Chaque carré est appelé élément ou entrée. Nous représenterons chaque élément avec un point ( .) dans les diagrammes ci-dessous:

Matrice 2 × 2

. .
. .

Matrice 3 × 3

. . .
. . .
. . .

Matrice 4 × 4

. . . .
. . . .
. . . .
. . . .

Alors, que signifie faire pivoter une matrice? Prenons une matrice 2 × 2 et mettons quelques nombres dans chaque élément afin que la rotation puisse être observée:

0 1
2 3

Une rotation de 90 degrés nous donne:

2 0
3 1

Nous avons littéralement tourné toute la matrice une fois vers la droite, tout comme le volant d'une voiture. Il peut être utile de penser à «basculer» la matrice sur son côté droit. Nous voulons écrire une fonction, en Python, qui prend une matrice et tourne une fois vers la droite. La signature de la fonction sera:

def rotate(matrix):
    # Algorithm goes here.

La matrice sera définie à l'aide d'un tableau à deux dimensions:

matrix = [
    [0,1],
    [2,3]
]

Par conséquent, la première position d'index accède à la ligne. La deuxième position d'index accède à la colonne:

matrix[row][column]

Nous allons définir une fonction utilitaire pour imprimer une matrice.

def print_matrix(matrix):
    for row in matrix:
        print row

Une méthode de rotation d'une matrice consiste à le faire couche par couche. Mais qu'est-ce qu'une couche? Pensez à un oignon. Tout comme les couches d'un oignon, à mesure que chaque couche est retirée, nous nous déplaçons vers le centre. D'autres analogies sont une poupée Matryoshka ou un jeu de passe-le-colis.

La largeur et la hauteur d'une matrice déterminent le nombre de couches dans cette matrice. Utilisons différents symboles pour chaque couche:

Une matrice 2 × 2 a 1 couche

. .
. .

Une matrice 3 × 3 a 2 couches

. . .
. x .
. . .

Une matrice 4 × 4 a 2 couches

. . . .
. x x .
. x x .
. . . .

Une matrice 5 × 5 a 3 couches

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

Une matrice 6 × 6 a 3 couches

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

Une matrice 7 × 7 a 4 couches

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

Vous remarquerez peut-être que l'augmentation de la largeur et de la hauteur d'une matrice n'augmente pas toujours le nombre de couches. En prenant les matrices ci-dessus et en tabulant les couches et les dimensions, nous voyons le nombre de couches augmenter une fois tous les deux incréments de largeur et de hauteur:

+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 |      1 |
| 2×2 |      1 |
| 3×3 |      2 |
| 4×4 |      2 |
| 5×5 |      3 |
| 6×6 |      3 |
| 7×7 |      4 |
+-----+--------+

Cependant, toutes les couches n'ont pas besoin de tourner. Une matrice 1 × 1 est la même avant et après rotation. La couche centrale 1 × 1 est toujours la même avant et après la rotation, quelle que soit la taille de la matrice globale:

+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 |      1 |                0 |
| 2×2 |      1 |                1 |
| 3×3 |      2 |                1 |
| 4×4 |      2 |                2 |
| 5×5 |      3 |                2 |
| 6×6 |      3 |                3 |
| 7×7 |      4 |                3 |
+-----+--------+------------------+

Étant donné la matrice N × N, comment pouvons-nous déterminer par programme le nombre de couches dont nous avons besoin de tourner? Si nous divisons la largeur ou la hauteur par deux et ignorons le reste, nous obtenons les résultats suivants.

+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers |   N/2   |
+-----+--------+------------------+---------+
| 1×1 |      1 |                0 | 1/2 = 0 |
| 2×2 |      1 |                1 | 2/2 = 1 |
| 3×3 |      2 |                1 | 3/2 = 1 |
| 4×4 |      2 |                2 | 4/2 = 2 |
| 5×5 |      3 |                2 | 5/2 = 2 |
| 6×6 |      3 |                3 | 6/2 = 3 |
| 7×7 |      4 |                3 | 7/2 = 3 |
+-----+--------+------------------+---------+

Remarquez comment N/2correspond le nombre de couches à faire pivoter? Parfois, le nombre de couches rotatives est inférieur de un au nombre total de couches dans la matrice. Cela se produit lorsque la couche la plus interne est formée d'un seul élément (c'est-à-dire une matrice 1 × 1) et n'a donc pas besoin d'être tournée. Il est simplement ignoré.

Nous aurons sans aucun doute besoin de ces informations dans notre fonction pour faire pivoter une matrice, alors ajoutons-la maintenant:

def rotate(matrix):
    size = len(matrix)
    # Rotatable layers only.
    layer_count = size / 2

Maintenant que nous savons ce que sont les calques et comment déterminer le nombre de calques qui doivent réellement être tournés, comment isoler un seul calque pour pouvoir le faire pivoter? Tout d'abord, nous inspectons une matrice de la couche la plus externe, vers l'intérieur, jusqu'à la couche la plus interne. Une matrice 5 × 5 a trois couches au total et deux couches qui nécessitent une rotation:

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

Regardons d'abord les colonnes. La position des colonnes définissant la couche la plus externe, en supposant que nous comptons à partir de 0, est 0 et 4:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

0 et 4 sont également les positions des lignes pour la couche la plus externe.

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

Ce sera toujours le cas puisque la largeur et la hauteur sont les mêmes. Par conséquent, nous pouvons définir les positions des colonnes et des lignes d'une couche avec seulement deux valeurs (plutôt que quatre).

En se déplaçant vers la deuxième couche, la position des colonnes est 1 et 3. Et, oui, vous l'avez deviné, c'est la même chose pour les lignes. Il est important de comprendre que nous devions à la fois incrémenter et décrémenter les positions des lignes et des colonnes lors du déplacement vers la couche suivante.

+-----------+---------+---------+---------+
|   Layer   |  Rows   | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes     |
| Inner     | 1 and 3 | 1 and 3 | Yes     |
| Innermost | 2       | 2       | No      |
+-----------+---------+---------+---------+

Donc, pour inspecter chaque couche, nous voulons une boucle avec des compteurs à la fois croissants et décroissants qui représentent le déplacement vers l'intérieur, à partir de la couche la plus externe. Nous appellerons cela notre «boucle de couches».

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1
        print 'Layer %d: first: %d, last: %d' % (layer, first, last)

# 5x5 matrix
matrix = [
    [ 0, 1, 2, 3, 4],
    [ 5, 6, 6, 8, 9],
    [10,11,12,13,14],
    [15,16,17,18,19],
    [20,21,22,23,24]
]

rotate(matrix)

Le code ci-dessus parcourt les positions (ligne et colonne) de tous les calques nécessitant une rotation.

Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3

Nous avons maintenant une boucle fournissant les positions des lignes et des colonnes de chaque couche. Les variables firstet lastidentifient la position d'index des première et dernière lignes et colonnes. Revenons à nos tableaux de lignes et de colonnes:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

Nous pouvons donc naviguer à travers les couches d'une matrice. Maintenant, nous avons besoin d'un moyen de naviguer dans une couche afin de pouvoir déplacer des éléments autour de cette couche. Notez que les éléments ne «sautent» jamais d'un calque à un autre, mais ils se déplacent dans leurs calques respectifs.

La rotation de chaque élément d'un calque fait pivoter l'ensemble du calque. La rotation de tous les calques d'une matrice fait pivoter la matrice entière. Cette phrase est très importante, alors faites de votre mieux pour la comprendre avant de continuer.

Maintenant, nous avons besoin d'un moyen de déplacer réellement les éléments, c'est-à-dire de faire pivoter chaque élément, puis la couche, et finalement la matrice. Pour plus de simplicité, nous allons revenir à une matrice 3x3 - qui a une couche rotative.

0 1 2
3 4 5
6 7 8

Notre boucle de couche fournit les index des première et dernière colonnes, ainsi que les première et dernière lignes:

+-----+-------+
| Col | 0 1 2 |
+-----+-------+
|     | 0 1 2 |
|     | 3 4 5 |
|     | 6 7 8 |
+-----+-------+

+-----+-------+
| Row |       |
+-----+-------+
|   0 | 0 1 2 |
|   1 | 3 4 5 |
|   2 | 6 7 8 |
+-----+-------+

Parce que nos matrices sont toujours carrées, nous n'avons besoin que de deux variables firstet last, puisque les positions d'index sont les mêmes pour les lignes et les colonnes.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Our layer loop i=0, i=1, i=2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        # We want to move within a layer here.

Les variables première et dernière peuvent facilement être utilisées pour référencer les quatre coins d'une matrice. En effet, les coins eux-mêmes peuvent être définis en utilisant différentes permutations de firstet last(sans soustraction, addition ou décalage de ces variables):

+---------------+-------------------+-------------+
| Corner        | Position          | 3x3 Values  |
+---------------+-------------------+-------------+
| top left      | (first, first)    | (0,0)       |
| top right     | (first, last)     | (0,2)       |
| bottom right  | (last, last)      | (2,2)       |
| bottom left   | (last, first)     | (2,0)       |
+---------------+-------------------+-------------+

Pour cette raison, nous commençons notre rotation aux quatre coins extérieurs - nous allons les faire pivoter en premier. Soulignons-les avec *.

* 1 *
3 4 5
* 7 *

Nous voulons échanger chacun *avec le *à droite de celui-ci. Alors allons-y, imprimons nos coins définis en utilisant uniquement différentes permutations de firstet last:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = (first, first)
        top_right = (first, last)
        bottom_right = (last, last)
        bottom_left = (last, first)

        print 'top_left: %s' % (top_left)
        print 'top_right: %s' % (top_right)
        print 'bottom_right: %s' % (bottom_right)
        print 'bottom_left: %s' % (bottom_left)

matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]

rotate(matrix)

La sortie doit être:

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)

Maintenant, nous pouvons facilement échanger chacun des coins de notre boucle de calque:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = matrix[first][first]
        top_right = matrix[first][last]
        bottom_right = matrix[last][last]
        bottom_left = matrix[last][first]

        # bottom_left -> top_left
        matrix[first][first] = bottom_left
        # top_left -> top_right
        matrix[first][last] = top_left
        # top_right -> bottom_right
        matrix[last][last] = top_right
        # bottom_right -> bottom_left
        matrix[last][first] = bottom_right


print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)

Matrice avant de tourner les coins:

[0, 1, 2]
[3, 4, 5]
[6, 7, 8]

Matrice après rotation des coins:

[6, 1, 0]
[3, 4, 5]
[8, 7, 2]

Génial! Nous avons réussi à faire pivoter chaque coin de la matrice. Mais, nous n'avons pas fait pivoter les éléments au milieu de chaque couche. De toute évidence, nous avons besoin d'un moyen d'itérer au sein d'une couche.

Le problème est que la seule boucle de notre fonction jusqu'à présent (notre boucle de couche) passe à la couche suivante à chaque itération. Étant donné que notre matrice n'a qu'une seule couche rotative, la boucle de couche se termine après avoir tourné uniquement les coins. Voyons ce qui se passe avec une matrice 5 × 5 plus grande (où deux couches doivent tourner). Le code de fonction a été omis, mais il reste le même que ci-dessus:

matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)

La sortie est:

[20,  1,  2,  3,  0]
[ 5, 16,  7,  6,  9]
[10, 11, 12, 13, 14]
[15, 18, 17,  8, 19]
[24, 21, 22, 23,  4]

Il ne devrait pas être surprenant que les coins de la couche la plus externe aient été tournés, mais vous pouvez également remarquer que les coins de la couche suivante (vers l'intérieur) ont également été tournés. C'est logique. Nous avons écrit du code pour naviguer à travers les couches et également pour faire pivoter les coins de chaque couche. Cela ressemble à un progrès, mais malheureusement, nous devons prendre du recul. Il est tout simplement inutile de passer au calque suivant tant que le calque précédent (extérieur) n'a pas été complètement tourné. Autrement dit, jusqu'à ce que chaque élément du calque ait été tourné. Faire tourner uniquement les coins ne fera pas l'affaire!

Respirez profondément. Nous avons besoin d'une autre boucle. Une boucle imbriquée pas moins. La nouvelle boucle imbriquée utilisera les variables firstet last, plus un décalage pour naviguer dans une couche. Nous appellerons cette nouvelle boucle notre «boucle d'élément». La boucle d'élément visitera chaque élément le long de la rangée supérieure, chaque élément en bas à droite, chaque élément le long de la rangée inférieure et chaque élément en haut à gauche.

• Pour avancer le long de la ligne supérieure, l'index de colonne doit être incrémenté.
• En descendant vers la droite, l'index de ligne doit être incrémenté.
• Pour reculer le long du bas, l'index de colonne doit être décrémenté.
• Le déplacement vers le haut à gauche nécessite la diminution de l'index de ligne.

Cela semble complexe, mais c'est facile car le nombre de fois que nous incrémentons et décrémentons pour atteindre ce qui précède reste le même sur les quatre côtés de la matrice. Par exemple:

• Déplacez 1 élément sur la rangée supérieure.
• Déplacez 1 élément sur le côté droit.
• Déplacez 1 élément vers l'arrière le long de la rangée inférieure.
• Déplacez 1 élément vers le haut à gauche.

Cela signifie que nous pouvons utiliser une seule variable en combinaison avec les variables firstet lastpour nous déplacer dans une couche. Il peut être utile de noter que le déplacement sur la rangée supérieure et sur le côté droit nécessite une incrémentation. Tout en se déplaçant vers l'arrière le long du bas et vers le haut du côté gauche, les deux nécessitent une décrémentation.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Move through layers (i.e. layer loop).
    for layer in range(0, layer_count):

            first = layer
            last = size - first - 1

            # Move within a single layer (i.e. element loop).
            for element in range(first, last):

                offset = element - first

                # 'element' increments column (across right)
                top_element = (first, element)
                # 'element' increments row (move down)
                right_side = (element, last)
                # 'last-offset' decrements column (across left)
                bottom = (last, last-offset)
                # 'last-offset' decrements row (move up)
                left_side = (last-offset, first)

                print 'top: %s' % (top)
                print 'right_side: %s' % (right_side)
                print 'bottom: %s' % (bottom)
                print 'left_side: %s' % (left_side)

Maintenant, nous devons simplement affecter le haut au côté droit, le côté droit au bas, le bas au côté gauche et le côté gauche au haut. En rassemblant tout cela, nous obtenons:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1

        for element in range(first, last):
            offset = element - first

            top = matrix[first][element]
            right_side = matrix[element][last]
            bottom = matrix[last][last-offset]
            left_side = matrix[last-offset][first]

            matrix[first][element] = left_side
            matrix[element][last] = top
            matrix[last][last-offset] = right_side
            matrix[last-offset][first] = bottom

Compte tenu de la matrice:

0,  1,  2  
3,  4,  5  
6,  7,  8 

Notre rotatefonction se traduit par:

6,  3,  0  
7,  4,  1  
8,  5,  2  

Python:

rotated = list(zip(*original[::-1]))

et dans le sens antihoraire:

rotated_ccw = list(zip(*original))[::-1]

Comment cela fonctionne:

zip(*original)permutera les axes des tableaux 2D en empilant les éléments correspondants des listes dans de nouvelles listes. (L' *opérateur indique à la fonction de distribuer les listes contenues dans des arguments)

>>> list(zip(*[[1,2,3],[4,5,6],[7,8,9]]))
[[1,4,7],[2,5,8],[3,6,9]]

L' [::-1]instruction inverse les éléments du tableau (veuillez consulter les tranches étendues ou cette question ):

>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]

Enfin, la combinaison des deux entraînera la transformation de rotation.

Le changement de placement de [::-1] inversera les listes à différents niveaux de la matrice.

En voici un qui effectue la rotation en place au lieu d'utiliser un tout nouveau tableau pour conserver le résultat. J'ai laissé l'initialisation de la matrice et l'imprimer. Cela ne fonctionne que pour les tableaux carrés, mais ils peuvent être de n'importe quelle taille. La surcharge de mémoire est égale à la taille d'un élément du tableau afin que vous puissiez faire la rotation d'un tableau aussi grand que vous le souhaitez.

int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
    for (int j = i; j < n - i - 1; j++)
    {
        tmp             = a[i][j];
        a[i][j]         = a[j][n-i-1];
        a[j][n-i-1]     = a[n-i-1][n-j-1];
        a[n-i-1][n-j-1] = a[n-j-1][i];
        a[n-j-1][i]     = tmp;
    }
}

Il y a des tonnes de bon code ici, mais je veux juste montrer ce qui se passe géométriquement afin que vous puissiez mieux comprendre la logique du code. Voici comment j'aborderais cela.

tout d'abord, ne confondez pas cela avec une transposition qui est très facile ..

l'idée de base est de le traiter comme des couches et nous faisons tourner une couche à la fois ..

disons que nous avons un 4x4

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

après l'avoir tourné dans le sens horaire de 90, nous obtenons

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

décomposons donc cela, nous tournons d'abord les 4 coins essentiellement

1           4


13          16

puis nous tournons le diamant suivant qui est en quelque sorte de travers

    2
            8
9       
        15

puis le 2e diamant asymétrique

        3
5           
            12
    14

donc ça prend soin du bord extérieur donc essentiellement on fait ça une coquille à la fois jusqu'à

enfin le carré du milieu (ou si c'est bizarre juste le dernier élément qui ne bouge pas)

6   7
10  11

alors maintenant, calculons les indices de chaque couche, supposons que nous travaillons toujours avec la couche la plus externe, nous faisons

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

ainsi de suite et ainsi de suite jusqu'à ce que nous soyons à mi-chemin à travers le bord

donc en général le motif est

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

Comme je l'ai dit dans mon post précédent, voici du code en C # qui implémente une rotation de matrice O (1) pour n'importe quelle matrice de taille. Pour plus de concision et de lisibilité, il n'y a pas de vérification d'erreur ou de vérification de plage. Le code:

static void Main (string [] args)
{
  int [,]
    //  create an arbitrary matrix
    m = {{0, 1}, {2, 3}, {4, 5}};

  Matrix
    //  create wrappers for the data
    m1 = new Matrix (m),
    m2 = new Matrix (m),
    m3 = new Matrix (m);

  //  rotate the matricies in various ways - all are O(1)
  m1.RotateClockwise90 ();
  m2.Rotate180 ();
  m3.RotateAnitclockwise90 ();

  //  output the result of transforms
  System.Diagnostics.Trace.WriteLine (m1.ToString ());
  System.Diagnostics.Trace.WriteLine (m2.ToString ());
  System.Diagnostics.Trace.WriteLine (m3.ToString ());
}

class Matrix
{
  enum Rotation
  {
    None,
    Clockwise90,
    Clockwise180,
    Clockwise270
  }

  public Matrix (int [,] matrix)
  {
    m_matrix = matrix;
    m_rotation = Rotation.None;
  }

  //  the transformation routines
  public void RotateClockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
  }

  public void Rotate180 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
  }

  public void RotateAnitclockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
  }

  //  accessor property to make class look like a two dimensional array
  public int this [int row, int column]
  {
    get
    {
      int
        value = 0;

      switch (m_rotation)
      {
      case Rotation.None:
        value = m_matrix [row, column];
        break;

      case Rotation.Clockwise90:
        value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
        break;

      case Rotation.Clockwise180:
        value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
        break;

      case Rotation.Clockwise270:
        value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
        break;
      }

      return value;
    }

    set
    {
      switch (m_rotation)
      {
      case Rotation.None:
        m_matrix [row, column] = value;
        break;

      case Rotation.Clockwise90:
        m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
        break;

      case Rotation.Clockwise180:
        m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
        break;

      case Rotation.Clockwise270:
        m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
        break;
      }
    }
  }

  //  creates a string with the matrix values
  public override string ToString ()
  {
    int
      num_rows = 0,
      num_columns = 0;

    switch (m_rotation)
    {
    case Rotation.None:
    case Rotation.Clockwise180:
      num_rows = m_matrix.GetUpperBound (0);
      num_columns = m_matrix.GetUpperBound (1);
      break;

    case Rotation.Clockwise90:
    case Rotation.Clockwise270:
      num_rows = m_matrix.GetUpperBound (1);
      num_columns = m_matrix.GetUpperBound (0);
      break;
    }

    StringBuilder
      output = new StringBuilder ();

    output.Append ("{");

    for (int row = 0 ; row <= num_rows ; ++row)
    {
      if (row != 0)
      {
        output.Append (", ");
      }

      output.Append ("{");

      for (int column = 0 ; column <= num_columns ; ++column)
      {
        if (column != 0)
        {
          output.Append (", ");
        }

        output.Append (this [row, column].ToString ());
      }

      output.Append ("}");
    }

    output.Append ("}");

    return output.ToString ();
  }

  int [,]
    //  the original matrix
    m_matrix;

  Rotation
    //  the current view of the matrix
    m_rotation;
}

OK, je vais lever la main, il ne fait aucune modification au tableau d'origine lors de la rotation. Mais, dans un système OO, cela n'a pas d'importance tant que l'objet semble avoir été tourné vers les clients de la classe. À l'heure actuelle, la classe Matrix utilise des références aux données du tableau d'origine, donc la modification de toute valeur de m1 modifiera également m2 et m3. Une petite modification apportée au constructeur pour créer un nouveau tableau et y copier les valeurs triera cela.

Alors que la rotation des données en place peut être nécessaire (peut-être pour mettre à jour la représentation stockée physiquement), il devient plus simple et peut-être plus performant d'ajouter une couche d'indirection sur l'accès au tableau, peut-être une interface:

interface IReadableMatrix
{
    int GetValue(int x, int y);
}

Si votre Matriximplémente déjà cette interface, vous pouvez la faire pivoter via une classe décoratrice comme celle-ci:

class RotatedMatrix : IReadableMatrix
{
    private readonly IReadableMatrix _baseMatrix;

    public RotatedMatrix(IReadableMatrix baseMatrix)
    {
        _baseMatrix = baseMatrix;
    }

    int GetValue(int x, int y)
    {
        // transpose x and y dimensions
        return _baseMatrix(y, x);
    }
}

Une rotation de + 90 / -90 / 180 degrés, un retournement horizontal / vertical et une mise à l'échelle peuvent également être obtenus de cette manière.

Les performances devraient être mesurées dans votre scénario spécifique. Cependant, l'opération O (n ^ 2) a maintenant été remplacée par un appel O (1). C'est un appel de méthode virtuel qui est plus lent que l'accès direct au tableau, il dépend donc de la fréquence à laquelle le tableau pivoté est utilisé après la rotation. Si elle est utilisée une fois, cette approche gagnerait définitivement. S'il est tourné puis utilisé dans un système de longue durée pendant des jours, alors la rotation en place pourrait mieux fonctionner. Cela dépend également si vous pouvez accepter le coût initial.

Comme pour tous les problèmes de performance, mesurez, mesurez, mesurez!

C'est une meilleure version de celui-ci en Java: je l'ai fait pour une matrice avec une largeur et une hauteur différentes

• h est ici la hauteur de la matrice après rotation
• w est ici la largeur de la matrice après rotation

public int[][] rotateMatrixRight(int[][] matrix)
{
    /* W and H are already swapped */
    int w = matrix.length;
    int h = matrix[0].length;
    int[][] ret = new int[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ret[i][j] = matrix[w - j - 1][i];
        }
    }
    return ret;
}


public int[][] rotateMatrixLeft(int[][] matrix)
{
    /* W and H are already swapped */
    int w = matrix.length;
    int h = matrix[0].length;   
    int[][] ret = new int[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ret[i][j] = matrix[j][h - i - 1];
        }
    }
    return ret;
}

Ce code est basé sur le post de Nick Berardi.

Ruby-way: .transpose.map &:reverse

Il y a déjà beaucoup de réponses, et j'en ai trouvé deux revendiquant une complexité temporelle O (1). Le vrai algorithme O (1) consiste à laisser le stockage du tableau intact et à changer la façon dont vous indexez ses éléments. L'objectif ici est qu'il ne consomme pas de mémoire supplémentaire et qu'il ne nécessite pas de temps supplémentaire pour itérer les données.

Les rotations de 90, -90 et 180 degrés sont de simples transformations qui peuvent être effectuées tant que vous savez combien de lignes et de colonnes se trouvent dans votre réseau 2D; Pour faire pivoter un vecteur de 90 degrés, permutez les axes et annulez l'axe Y. Pour -90 degrés, permutez les axes et annulez l'axe X. Pour 180 degrés, annulez les deux axes sans permuter.

D'autres transformations sont possibles, telles que la mise en miroir horizontale et / ou verticale en annulant les axes indépendamment.

Cela peut être fait par exemple par une méthode d'accesseur. Les exemples ci-dessous sont des fonctions JavaScript, mais les concepts s'appliquent également à toutes les langues.

 // Get an array element in column/row order
 var getArray2d = function(a, x, y) {
   return a[y][x];
 };

 //demo
 var arr = [
   [5, 4, 6],
   [1, 7, 9],
   [-2, 11, 0],
   [8, 21, -3],
   [3, -1, 2]
 ];

 var newarr = [];
 arr[0].forEach(() => newarr.push(new Array(arr.length)));

 for (var i = 0; i < newarr.length; i++) {
   for (var j = 0; j < newarr[0].length; j++) {
     newarr[i][j] = getArray2d(arr, i, j);
   }
 }
 console.log(newarr);

// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
  var t = x;
  x = y;
  y = a.length - t - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
  var t = x;
  x = a[0].length - y - 1;
  y = t;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
  x = a[0].length - x - 1;
  y = a.length - y - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2d180(arr, i, j);
  }
}
console.log(newarr);

Ce code suppose un tableau de tableaux imbriqués, où chaque tableau interne est une ligne.

La méthode vous permet de lire (ou d'écrire) des éléments (même dans un ordre aléatoire) comme si le tableau avait été tourné ou transformé. Maintenant, choisissez la bonne fonction à appeler, probablement par référence, et c'est parti!

Le concept peut être étendu pour appliquer des transformations de manière additive (et non destructive) via les méthodes d'accesseur. Y compris les rotations d'angle arbitraires et la mise à l'échelle.

Quelques personnes ont déjà mis en place des exemples qui impliquent de créer un nouveau tableau.

Quelques autres choses à considérer:

(a) Au lieu de déplacer réellement les données, parcourez simplement le tableau "tourné" différemment.

(b) Faire la rotation sur place peut être un peu plus délicat. Vous aurez besoin d'un peu d'espace de travail (probablement à peu près égal à une ligne ou une colonne). Il existe un ancien document ACM sur les transpositions sur place ( http://doi.acm.org/10.1145/355719.355729 ), mais leur exemple de code est FORTRAN méchant et chargé.

Addenda:

http://doi.acm.org/10.1145/355611.355612 est un autre algorithme de transposition en place, soi-disant supérieur.

La réponse de Nick fonctionnerait également pour un tableau NxM avec seulement une petite modification (par opposition à un NxN).

string[,] orig = new string[n, m];
string[,] rot = new string[m, n];

...

for ( int i=0; i < n; i++ )
  for ( int j=0; j < m; j++ )
    rot[j, n - i - 1] = orig[i, j];

Une façon de penser à cela est que vous avez déplacé le centre de l'axe (0,0) du coin supérieur gauche vers le coin supérieur droit. Vous transposez simplement de l'un à l'autre.

Temps - O (N), Espace - O (1)

public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2; i++) {
        int last = n - 1 - i;
        for (int j = i; j < last; j++) {
            int top = matrix[i][j];
            matrix[i][j] = matrix[last - j][i];
            matrix[last - j][i] = matrix[last][last - j];
            matrix[last][last - j] = matrix[j][last];
            matrix[j][last] = top;
        }
    }
}

Voici ma version Ruby (notez que les valeurs ne sont pas affichées de la même manière, mais elles tournent toujours comme décrit).

def rotate(matrix)
  result = []
  4.times { |x|
    result[x] = []
    4.times { |y|
      result[x][y] = matrix[y][3 - x]
    }
  }

  result
end

matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]

def print_matrix(matrix)
  4.times { |y|
    4.times { |x|
      print "#{matrix[x][y]} "
    }
    puts ""
  }
end

print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))

Le résultat:

1 5 9 3 
2 6 0 4 
3 7 1 5 
4 8 2 6 

4 3 2 1 
8 7 6 5 
2 1 0 9 
6 5 4 3

voici une méthode de rotation dans l'espace, par java, uniquement pour le carré. pour un tableau 2d non carré, vous devrez de toute façon créer un nouveau tableau.

private void rotateInSpace(int[][] arr) {
    int z = arr.length;
    for (int i = 0; i < z / 2; i++) {
        for (int j = 0; j < (z / 2 + z % 2); j++) {
            int x = i, y = j;
            int temp = arr[x][y];
            for (int k = 0; k < 4; k++) {
                int temptemp = arr[y][z - x - 1];
                arr[y][z - x - 1] = temp;
                temp = temptemp;

                int tempX = y;
                y = z - x - 1;
                x = tempX;
            }
        }
    }
}

code pour faire pivoter n'importe quel tableau 2d de taille en créant un nouveau tableau:

private int[][] rotate(int[][] arr) {
    int width = arr[0].length;
    int depth = arr.length;
    int[][] re = new int[width][depth];
    for (int i = 0; i < depth; i++) {
        for (int j = 0; j < width; j++) {
            re[j][depth - i - 1] = arr[i][j];
        }
    }
    return re;
}

Implémentation du pseudocode +90 de fossette (par exemple transposer puis inverser chaque ligne) en JavaScript:

function rotate90(a){
  // transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
  a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
  // row reverse
  for (i in a){
    a[i] = a[i].reverse();
  }
  return a;
}

Vous pouvez le faire en 3 étapes simples :

1 ) Supposons que nous ayons une matrice

   1 2 3
   4 5 6
   7 8 9

2 ) Prendre la transposition de la matrice

   1 4 7
   2 5 8
   3 6 9

3 ) Échanger des lignes pour obtenir une matrice pivotée

   3 6 9
   2 5 8
   1 4 7

Code source Java pour cela:

public class MyClass {

    public static void main(String args[]) {
        Demo obj = new Demo();
        /*initial matrix to rotate*/
        int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[][] transpose = new int[3][3]; // matrix to store transpose

        obj.display(matrix);              // initial matrix

        obj.rotate(matrix, transpose);    // call rotate method
        System.out.println();
        obj.display(transpose);           // display the rotated matix
    }
}

class Demo {   
    public void rotate(int[][] mat, int[][] tran) {

        /* First take the transpose of the matrix */
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat.length; j++) {
                tran[i][j] = mat[j][i]; 
            }
        }

        /*
         * Interchange the rows of the transpose matrix to get rotated
         * matrix
         */
        for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
            for (int k = 0; k < tran.length; k++) {
                swap(i, k, j, k, tran);
            }
        }
    }

    public void swap(int a, int b, int c, int d, int[][] arr) {
        int temp = arr[a][b];
        arr[a][b] = arr[c][d];
        arr[c][d] = temp;    
    }

    /* Method to display the matrix */
    public void display(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Production:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 

Voici mon implémentation, en complexité mémoire C, O (1), rotation en place, 90 degrés dans le sens des aiguilles d'une montre:

#include <stdio.h>

#define M_SIZE 5

static void initMatrix();
static void printMatrix();
static void rotateMatrix();

static int m[M_SIZE][M_SIZE];

int main(void){
    initMatrix();
    printMatrix();
    rotateMatrix();
    printMatrix();

    return 0;
}

static void initMatrix(){
    int i, j;

    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            m[i][j] = M_SIZE*i + j + 1;
        }
    }
}

static void printMatrix(){
    int i, j;

    printf("Matrix\n");
    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            printf("%02d ", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

static void rotateMatrix(){
    int r, c;

    for(r = 0; r < M_SIZE/2; r++){
        for(c = r; c < M_SIZE - r - 1; c++){
            int tmp = m[r][c];

            m[r][c] = m[M_SIZE - c - 1][r];
            m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
            m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
            m[c][M_SIZE - r - 1] = tmp;
        }
    }
}

Voici la version Java:

public static void rightRotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
           int offset = i - first;
           int temp = matrix[first][i];
           matrix[first][i] = matrix[last-offset][first];
           matrix[last-offset][first] = matrix[last][last-offset];
           matrix[last][last-offset] = matrix[i][last];
           matrix[i][last] = temp;
        }
    }
}

la méthode fait d'abord pivoter le calque le plus externe, puis se déplace vers le calque intérieur de manière carrée.

D'un point de vue linéaire, considérons les matrices:

    1 2 3        0 0 1
A = 4 5 6    B = 0 1 0
    7 8 9        1 0 0

Maintenant, prenez une transposition

     1 4 7
A' = 2 5 8
     3 6 9

Et considérons l'action de A 'sur B, ou B sur A'.
Respectivement:

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
      9 6 3          1 4 7

Ceci est extensible pour n'importe quelle matrice nxn. Et appliquer ce concept rapidement dans le code:

void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
    mat[r1][c1] ^= mat[r2][c2];
    mat[r2][c2] ^= mat[r1][c1];
    mat[r1][c1] ^= mat[r2][c2];
}

void transpose(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = (i + 1); j < size; j++)
        {
            swapInSpace(mat, i, j, j, i);
        }
    }
}

void rotate(int** mat, int size)
{
    //Get transpose
    transpose(mat, size);

    //Swap columns
    for (int i = 0; i < size / 2; i++)
    {
        for (int j = 0; j < size; j++)
        {
            swapInSpace(mat, i, j, size - (i + 1), j);
        }
    }
}

Code C # pour faire pivoter [n, m] tableaux 2D à 90 degrés à droite

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MatrixProject
{
    // mattrix class

    class Matrix{
        private int rows;
        private int cols;
        private int[,] matrix;

        public Matrix(int n){
            this.rows = n;
            this.cols = n;
            this.matrix = new int[this.rows,this.cols];

        }

        public Matrix(int n,int m){
            this.rows = n;
            this.cols = m;

            this.matrix = new int[this.rows,this.cols];
        }

        public void Show()
        {
            for (var i = 0; i < this.rows; i++)
            {
                for (var j = 0; j < this.cols; j++) {
                    Console.Write("{0,3}", this.matrix[i, j]);
                }
                Console.WriteLine();
            }                
        }

        public void ReadElements()
        {
           for (var i = 0; i < this.rows; i++)
                for (var j = 0; j < this.cols; j++)
                {
                    Console.Write("element[{0},{1}]=",i,j);
                    this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
                }            
        }


        // rotate [n,m] 2D array by 90 deg right
        public void Rotate90DegRight()
        {

            // create a mirror of current matrix
            int[,] mirror = this.matrix;

            // create a new matrix
            this.matrix = new int[this.cols, this.rows];

            for (int i = 0; i < this.rows; i++)
            {
                for (int j = 0; j < this.cols; j++)
                {
                    this.matrix[j, this.rows - i - 1] = mirror[i, j];
                }
            }

            // replace cols count with rows count
            int tmp = this.rows;
            this.rows = this.cols;
            this.cols = tmp;           
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Matrix myMatrix = new Matrix(3,4);
            Console.WriteLine("Enter matrix elements:");
            myMatrix.ReadElements();
            Console.WriteLine("Matrix elements are:");
            myMatrix.Show();
            myMatrix.Rotate90DegRight();
            Console.WriteLine("Matrix rotated at 90 deg are:");
            myMatrix.Show();
            Console.ReadLine();
        }
    }
}

Résultat:

    Enter matrix elements:
    element[0,0]=1
    element[0,1]=2
    element[0,2]=3
    element[0,3]=4
    element[1,0]=5
    element[1,1]=6
    element[1,2]=7
    element[1,3]=8
    element[2,0]=9
    element[2,1]=10
    element[2,2]=11
    element[2,3]=12
    Matrix elements are:
      1  2  3  4
      5  6  7  8
      9 10 11 12
    Matrix rotated at 90 deg are:
      9  5  1
     10  6  2
     11  7  3
     12  8  4

PHP:

<?php    
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result

while(count($a)>0)
{
    $b[count($a[0])-1][] = array_shift($a[0]);
    if (count($a[0])==0)
    {
         array_shift($a);
    }
}

Depuis PHP5.6, la transposition de tableau peut être effectuée avec un sleak array_map() appel . En d'autres termes, les colonnes sont converties en lignes.

Code: ( Démo )

$array = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 0, 1, 2],
    [3, 4, 5, 6]
];
$transposed = array_map(null, ...$array);

$ transposé:

[
    [1, 5, 9, 3],
    [2, 6, 0, 4],
    [3, 7, 1, 5],
    [4, 8, 2, 6]
]

For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[X-i][j]

X est la taille du tableau dans lequel se trouve le graphique.

#transpose est une méthode standard de la classe Ruby's Array, donc:

% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] 
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]

L'implémentation est une fonction de transposition n ^ 2 écrite en C. Vous pouvez la voir ici: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose en choisissant "click" pour basculer la source "à côté de" transposer ".

Je me souviens mieux que les solutions O (n ^ 2), mais uniquement pour les matrices spécialement construites (telles que les matrices clairsemées)

Code C pour la rotation de la matrice à 90 degrés dans le sens horaire EN PLACE pour toute matrice M * N

void rotateInPlace(int * arr[size][size], int row, int column){
    int i, j;
    int temp = row>column?row:column;
    int flipTill = row < column ? row : column;
    for(i=0;i<flipTill;i++){
        for(j=0;j<i;j++){
            swapArrayElements(arr, i, j);
        }
    }

    temp = j+1;

    for(i = row>column?i:0; i<row; i++){
            for(j=row<column?temp:0; j<column; j++){
                swapArrayElements(arr, i, j);
            }
    }

    for(i=0;i<column;i++){
        for(j=0;j<row/2;j++){
            temp = arr[i][j];
            arr[i][j] = arr[i][row-j-1];
            arr[i][row-j-1] = temp;
        }
    }
}

voici mon implémentation In Place en C

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}

Voici ma tentative de rotation de la matrice à 90 degrés qui est une solution en 2 étapes en C. Transposez d'abord la matrice en place, puis échangez les cols.

#define ROWS        5
#define COLS        5

void print_matrix_b(int B[][COLS], int rows, int cols) 
{
    for (int i = 0; i <= rows; i++) {
        for (int j = 0; j <=cols; j++) {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }
}

void swap_columns(int B[][COLS], int l, int r, int rows)
{
    int tmp;
    for (int i = 0; i <= rows; i++) {
        tmp = B[i][l];
        B[i][l] = B[i][r];
        B[i][r] = tmp;
    }
}


void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
    int tmp;
    // Transpose the matrix first
    for (int i = 0; i <= rows; i++) {
        for (int j = i; j <=cols; j++) {
            tmp = B[i][j];
            B[i][j] = B[j][i];
            B[j][i] = tmp;
        }
    }
    // Swap the first and last col and continue until
    // the middle.
    for (int i = 0; i < (cols / 2); i++)
        swap_columns(B, i, cols - i, rows);
}



int _tmain(int argc, _TCHAR* argv[])
{
    int B[ROWS][COLS] = { 
                  {1, 2, 3, 4, 5}, 
                      {6, 7, 8, 9, 10},
                          {11, 12, 13, 14, 15},
                          {16, 17, 18, 19, 20},
                          {21, 22, 23, 24, 25}
                        };

    matrix_2d_rotation(B, ROWS - 1, COLS - 1);

    print_matrix_b(B, ROWS - 1, COLS -1);
    return 0;
}

@dagorym: Aw, mec. J'avais accroché à cela comme un bon puzzle "Je m'ennuie, que puis-je méditer". J'ai trouvé mon code de transposition en place, mais je suis arrivé ici pour trouver le vôtre à peu près identique au mien ... ah, eh bien. Le voici en Ruby.

require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }

pp a

0.upto(n/2-1) do |i|
  i.upto(n-i-2) do |j|
    tmp             = a[i][j]
    a[i][j]         = a[n-j-1][i]
    a[n-j-1][i]     = a[n-i-1][n-j-1]
    a[n-i-1][n-j-1] = a[j][n-i-1]
    a[j][n-i-1]     = tmp
  end
end

pp a

short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};

short rotated[4][4];

for (int r = 0; r < 4; ++r)
{
  for (int c = 0; c < 4; ++c)
  {
    rotated[r][c] = normal[c][3-r];
  }
}

Méthode C ++ simple, alors il y aurait une grosse surcharge de mémoire dans un grand tableau.