Comment faire pivoter un tableau à deux dimensions ?
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Inspiré par Message de Raymond Chen, disons que vous avez un tableau bidimensionnel 4x4, écrivez une fonction qui le fait pivoter de 90 degrés.Raymond crée un lien vers une solution en pseudo-code, mais j'aimerais voir des éléments 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 faisait 10 000 x 10 000 ?
La solution
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;
}
Autres conseils
Algorithme de temps O(n^2) et d'espace O(1) (sans aucune solution de contournement ni trucs hanky-panky !)
Rotation de +90 :
- Transposer
- Inverser chaque ligne
Rotation de -90 :
Méthode 1 :
- Transposer
- Inverser chaque colonne
Méthode 2 :
- Inverser chaque ligne
- Transposer
Rotation de +180 :
Méthode 1:Rotation de +90 deux fois
Méthode 2:Inversez chaque ligne puis inversez chaque colonne (Transpose)
Rotation de -180 :
Méthode 1:Rotation de -90 deux fois
Méthode 2:Inversez chaque colonne puis inversez chaque ligne
Méthode 3:Faites pivoter de +180 car ils sont identiques
J'aimerais 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 volontairement répétitif.La solution proposée ici n'est pas la plus compacte syntaxiquement, elle est cependant destinée à ceux qui souhaitent apprendre 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 est simplement une grille dont la largeur et la hauteur sont les mêmes.Notez que la largeur et la hauteur d'une matrice peuvent être différentes, mais par souci de simplicité, 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.
Des exemples de matrices sont :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é un élément ou une entrée.Nous représenterons chaque élément par un point (.) dans les schémas 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 pour 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 nous tournions le volant d'une voiture.Il peut être utile de penser à « faire 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 pour faire pivoter 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, au fur et à mesure que chaque couche est retirée, on se déplace vers le centre.D'autres analogies sont un Poupée Matriochka ou un jeu de passe-colis.
La largeur et la hauteur d'une matrice dictent 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’incrémentation de un 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 tablant les couches et les dimensions, nous voyons le nombre de couches augmenter une fois pour 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 d’être pivotées.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 que nous devons faire pivoter ?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/2 correspond au nombre de couches qui doivent être pivotées ?Parfois, le nombre de couches rotatives est inférieur d’une 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-à-direune matrice 1×1) et n’a donc pas besoin d’être pivoté.Cela est tout simplement ignoré.
Nous aurons sans doute besoin de cette information 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 nécessitent réellement une rotation, comment isoler un seul calque afin de pouvoir le faire pivoter ?Tout d’abord, nous inspectons une matrice depuis la couche la plus externe, vers l’intérieur, jusqu’à la couche la plus interne.Une matrice 5×5 comporte trois couches au total et deux couches qui doivent être tournées :
. . . . .
. 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 l'on compte à 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 de 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’un calque avec seulement deux valeurs (au lieu de quatre).
En entrant dans la deuxième couche, la position des colonnes est 1 et 3.Et oui, vous l’aurez deviné, c’est pareil pour les lignes.Il est important de comprendre que nous avons dû à la fois incrémenter et décrémenter les positions des lignes et des colonnes lors du passage à 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 |
+-----------+---------+---------+---------+
Ainsi, pour inspecter chaque couche, nous voulons une boucle avec des compteurs croissants et décroissants qui représentent le mouvement vers l’intérieur, en commençant par 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 qui doivent être pivotés.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
Nous disposons désormais d'une boucle fournissant les positions des lignes et des colonnes de chaque couche.Les variables first et last identifier la position d'index de la première et de la dernière ligne et colonne.En revenant à 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 ainsi naviguer à travers les couches d’une matrice.Nous avons maintenant besoin d'un moyen de naviguer dans un calque afin de pouvoir déplacer des éléments autour de ce calque.Notez que les éléments ne « sautent » jamais d’un calque à un autre, mais ils se déplacent au sein de leurs calques respectifs.
La rotation de chaque élément d’un calque fait pivoter le calque entier.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 réellement déplacer les éléments, c'est-à-direfaites pivoter chaque élément, puis le calque, et finalement la matrice.Pour plus de simplicité, nous reviendrons à une matrice 3x3, dotée d'un calque rotatif.
0 1 2
3 4 5
6 7 8
Notre boucle de couches fournit les index de la première et de la dernière colonne, ainsi que de la première et de la dernière ligne :
+-----+-------+
| 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, first et 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 first et last 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 à l'aide de diverses permutations de first et 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 les ferons pivoter en premier.Mettons-les en valeur avec *.
* 1 *
3 4 5
* 7 *
Nous voulons échanger chacun * avec le * à droite de celui-ci.Alors allons-y et imprimons nos coins définis en utilisant uniquement diverses permutations de first et 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)
Le résultat doit être :
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
Maintenant, nous pourrions très facilement échanger chacun des coins depuis 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 rotation des 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]
Super!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 calque.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'un seul calque rotatif, la boucle des calques se termine après avoir fait pivoter uniquement les coins.Regardons 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)
Le résultat 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 du calque le plus externe aient été pivotés, mais vous remarquerez peut-être également que les coins du calque suivant (vers l’intérieur) ont également été pivotés.C'est logique.Nous avons écrit du code pour naviguer à travers les calques et également pour faire pivoter les coins de chaque calque.Cela semble être un progrès, mais nous devons malheureusement prendre du recul.Il ne sert à rien de passer au calque suivant tant que le calque précédent (externe) n'a pas été complètement pivoté.Autrement dit, jusqu'à ce que chaque élément du calque ait subi une rotation.Faire pivoter uniquement les coins ne suffira pas !
Respirez profondément.Nous avons besoin d'une autre boucle.Une boucle imbriquée rien de moins.La nouvelle boucle imbriquée utilisera le first et last variables, plus un décalage pour naviguer dans une couche.Nous appellerons cette nouvelle boucle notre « boucle d’éléments ».La boucle d'éléments visitera chaque élément de la rangée supérieure, chaque élément du côté droit, chaque élément de la rangée du bas et chaque élément du côté gauche.
- Pour avancer le long de la ligne supérieure, l'index de la colonne est incrémenté.
- Descendant le côté droit nécessite l'intégration de l'indice de ligne.
- Le déplacement vers l'arrière le long du bas nécessite que l'index de colonne soit décrément.
- Le montage du côté gauche nécessite que l'indice de ligne soit décrémenté.
Cela semble complexe, mais cela est rendu facile car le nombre de fois que nous incrémentons et décrémentons pour obtenir 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 vers le bas du côté droit.
- Déplacez 1 élément vers l’arrière le long de la ligne du bas.
- Déplacez 1 élément sur le côté gauche.
Cela signifie que nous pouvons utiliser une seule variable en combinaison avec le first et last variables à déplacer dans un calque.Il peut être utile de noter que le déplacement sur la rangée supérieure et sur le côté droit nécessite tous deux une incrémentation.Lors du déplacement 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)
Il nous suffit maintenant d'attribuer le haut au côté droit, le côté droit en bas, le bas au côté gauche et le côté gauche au haut.En mettant tout cela ensemble, 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
Étant donné la matrice :
0, 1, 2
3, 4, 5
6, 7, 8
Notre rotate la fonction donne :
6, 3, 0
7, 4, 1
8, 5, 2
Python:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
Pas cher, je sais.
Et dans le sens inverse des aiguilles d'une montre :
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
Comment cela fonctionne : (Demandé dans les commentaires)
zip(*original) échangera les axes des tableaux 2D en empilant les éléments correspondants des listes dans de nouvelles listes.(Le * l'opérateur indique à la fonction de distribuer les listes contenues en arguments)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
Le [::-1] L'instruction inverse les éléments du tableau (veuillez consulter Tranches étendues).
>>> [[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 dans différents niveaux de la matrice.
En voici un qui effectue la rotation sur place au lieu d'utiliser un tout nouveau tableau pour conserver le résultat.J'ai laissé l'initialisation du tableau 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, vous pouvez donc effectuer 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 un peu mieux comprendre la logique du code.Voici comment j’aborderais cela.
tout d'abord, ne confondez pas cela avec la transposition qui est très simple.
l'idée de base est de le traiter comme des calques et de faire pivoter un calque à 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 fait tourner de 90 dans le sens des aiguilles d'une montre, nous obtenons
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
alors décomposons cela, d'abord nous faisons pivoter les 4 coins essentiellement
1 4
13 16
puis on fait tourner le diamant suivant qui est en quelque sorte de travers
2
8
9
15
et puis le 2ème diamant asymétrique
3
5
12
14
donc cela prend soin du bord extérieur, donc essentiellement, nous faisons cela une coque à la fois jusqu'à ce que
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, trouvons 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 jusqu'à ce que nous soyons à mi-chemin à travers le bord
donc en général le modèle 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 article précédent, voici du code en C# qui implémente une rotation de matrice O(1) pour n'importe quelle taille de matrice.Par souci de concision et de lisibilité, il n'y a pas de vérification des erreurs ni de vérification de la 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 lève la main, cela n'apporte 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.Pour le moment, 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 du constructeur pour créer un nouveau tableau et y copier les valeurs réglera ce problème.
Bien qu'une rotation des données sur place puisse être nécessaire (peut-être pour mettre à jour la représentation physiquement stockée), 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 ton Matrix implémente déjà cette interface, elle peut alors être tournée via un décorateur classe comme ceci :
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);
}
}
La rotation de +90/-90/180 degrés, le retournement horizontal/vertical et la mise à l'échelle peuvent également être réalisés de cette manière.
Les performances devront être mesurées dans votre scénario spécifique.Cependant, l'opération O(n^2) a désormais été remplacée par un appel O(1).C'est un appel de méthode virtuelle qui est plus lent que l'accès direct au tableau, cela dépend donc de la fréquence d'utilisation du tableau pivoté après la rotation.Si elle est utilisée une seule fois, cette approche sera certainement gagnante.S'il est pivoté puis utilisé dans un système de longue durée pendant des jours, la rotation sur place pourrait alors fonctionner mieux.Cela dépend aussi si vous pouvez accepter le coût initial.
Comme pour tous les problèmes de performance, mesurez, mesurez, mesurez !
C'est une meilleure version 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 message de Nick Berardi.
À la manière de Ruby : .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 réel L'algorithme O(1) consiste à laisser le stockage du tableau intact et à modifier la façon dont vous indexez ses éléments.L’objectif ici est qu’il ne consomme pas de mémoire supplémentaire et ne nécessite pas non plus de temps supplémentaire pour itérer les données.
Les rotations de 90, -90 et 180 degrés sont des transformations simples qui peuvent être effectuées tant que vous savez combien de lignes et de colonnes se trouvent votre tableau 2D ;Pour faire pivoter n’importe quel vecteur de 90 degrés, échangez les axes et annulez l’axe Y.Pour -90 degrés, échangez les axes et annulez l'axe X.Pour 180 degrés, annulez les deux axes sans les échanger.
D'autres transformations sont possibles, comme la mise en miroir horizontalement et/ou verticalement en annulant les axes indépendamment.
Cela peut être fait par ex.une méthode d'accesseur.Les exemples ci-dessous sont des fonctions JavaScript, mais les concepts s'appliquent également à tous les langages.
// 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é pivoté ou transformé.Maintenant, choisissez simplement 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'accès.Y compris les rotations d'angle arbitraires et la mise à l'échelle.
Quelques personnes ont déjà donné des exemples impliquant la création d'un nouveau tableau.
Quelques autres éléments à considérer :
(a) Au lieu de déplacer réellement les données, parcourez simplement le tableau « pivoté » différemment.
(b) Effectuer la rotation sur place peut être un peu plus délicat.Vous aurez besoin d'un peu d'espace libre (probablement de taille à peu près égale à une ligne ou une colonne).Il existe un ancien article de l'ACM sur les transpositions sur place (http://doi.acm.org/10.1145/355719.355729), mais leur exemple de code est du FORTRAN chargé de goto.
Addenda:
http://doi.acm.org/10.1145/355611.355612 est un autre algorithme de transposition sur place, soi-disant supérieur.
celui de Nick La réponse 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 d'y penser 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 un tableau 2D de n'importe quelle 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 Dimple (par ex.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 dans 3 étapes faciles:
1)Supposons que nous ayons une matrice
1 2 3
4 5 6
7 8 9
2)Prendre la transposée de la matrice
1 4 7
2 5 8
3 6 9
3) Interchangez les lignes pour obtenir une matrice pivotée
3 6 9
2 5 8
1 4 7
Java code source pour ça:
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();
}
}
}
Sortir:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
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);
}
}
?>
Voici mon implémentation, en complexité mémoire C, O(1), en rotation sur place, de 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 la couche la plus externe, puis passe successivement à la couche interne.
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, prends une transposition
1 4 7
A' = 2 5 8
3 6 9
Et considérons l'action de A' sur B, ou de 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 n x n.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 de 90 degrés vers la 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
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 Array de Ruby, ainsi :
% 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.Tu peux le voir ici:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transposeen choisissant "cliquer pour basculer la source" à côté de "transposer".
Je me souviens mieux des 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 de 90 degrés dans le sens des aiguilles d'une montre 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 matricielle de 90 degrés qui est une solution en 2 étapes en C.Transposez d’abord la matrice en place, puis échangez les colonnes.
#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 :Oh mec.Je m'accrochais à cela comme à un bon casse-tête "Je m'ennuie, à quoi puis-je réfléchir".J'ai trouvé mon code de transposition sur 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, même s'il y aurait une surcharge de mémoire importante dans un grand tableau.
