Comment faites-vous pivoter un tableau bidimensionnel?

302

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?

swilliams
la source
99
Comment pourriez-vous vous en tirer avec moins de n ^ 2? Tous les éléments doivent être lus et définis, et il y a n ^ 2 éléments
erikkallen
9
Quel est votre n? Vous ne dites pas si le tableau 2D est carré (ce n'est pas dans le cas général! Par exemple, un vecteur est une matrice avec une dimension de 1), mais vous semblez impliquer que n est la largeur et la hauteur, et ont donc n² éléments . Il serait plus logique d'avoir n le nombre d'éléments, avec n = l × h.
niXar
1
Voici un moyen rapide de le faire: stocker les indices de ligne et de colonne (disons i et j). La transposition prend un temps constant (il suffit d'échanger les indices :). Vous pouvez faire de même avec les rotations (jouer avec les indices).
saadtaame
4
Dans le cas où n ^ 2 n'est pas réalisable. Vous pouvez créer une interface qui accède à chaque élément. Puis étant donné (i, j), appliquer une rotation pour (i, j) accéder à l'élément tourné et revenir. Ce n'est peut-être pas la meilleure solution mais ça marche.
Confondre

Réponses:

140

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;
}
Nick Berardi
la source
6
Bien sûr, mais qu'en est-il d'une solution utilisant la mémoire O (1)?
AlexeyMK
20
Votre solution a une complexité d'espace O (n ^ 2). Besoin de faire mieux
Kshitij Jain
6
Que diriez-vous de la matrice NXM?
Rohit
18
La complexité est linéaire dans le nombre d'éléments du tableau. Si N est le nombre d'éléments, la complexité est O (N). Si N est la longueur du côté, alors oui, la complexité est O (N ^ 2), mais c'est toujours optimal. Vous devez lire chaque élément au moins une fois. L'impression de la matrice est la même complexité
Alejandro
6
Pour une rotation de -90 degrés:ret[i][j] = matrix[j][n - i - 1]
Duncan Luk
387

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

85%
la source
4
Cela m'a été très utile; J'ai pu écrire un algorithme une fois que je connaissais la "version [pseudo-] code" de cette opération. Merci!
douma
13
Une de mes réponses SO préférées de tous les temps. Très instructif!
g33kz0r
2
Voici une implémentation JavaScript JSFiddle si quelqu'un est intéressé.
M. Polywhirl
6
Rotation de -90: (1) Inversez chaque rangée; (2) Transposer. Haskell: rotateCW = map reverse . transposeetrotateCCW = transpose . map reverse
Thomas Eding le
5
Quelle est la différence entre une rotation de 180 et -180?
Qian Chen
178

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  
Jack
la source
Au début, je me sentais comme "wow, la meilleure explication de tous les temps", mais après l'avoir lue plusieurs fois (pour m'assurer de ne rien manquer d'important dans la mer des mots), mon opinion a changé pour "l'homme, je comprends, peut on continue de bouger s'il vous plait? " Toujours voté pour avoir pris ce qui devait être des heures pour composer une réponse aussi élaborée.
Abhijit Sarkar
1
@AbhijitSarkar - Merci pour le vote positif et j'espère que cela a au moins aidé d'une petite manière. Bien sûr, vous avez raison, ma réponse est verbeuse. Ceci était cependant intentionnellement en contraste avec la grande majorité des réponses. Comme je l'ai dit au tout début de ma réponse: "Dans cette réponse, les concepts clés sont répétés, le rythme est lent et intentionnellement répétitif." Si vous avez des modifications qui gardent la clarté et la répétitivité nécessaires tout en réduisant le nombre de mots, je suis très ouvert aux suggestions. Ou modifiez simplement :)
Jack
@jack Vraiment une bonne explication. Cependant, je ne pouvais pas comprendre, comment avez-vous trouvé offset = élément - premier et dernier = taille - premier - 1? Ayant du mal à comprendre cela? En outre, le dernier décalage est-il le même que le décalage?
ashishjmeshram
1
TL; DR:list(zip(*reversed(your_list_of_lists)))
Boris
127

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.

bcdan
la source
3
Je crois que ce code provient de Peter Norvig: norvig.com/python-iaq.html
Josip
Vous pouvez utiliser zip(*reversed(original))au lieu de zip(*original[::-1])pour éviter de créer une copie supplémentaire de la liste d'origine.
Boris
70

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;
    }
}
dagorym
la source
Je peux voir au moins un bug. Si vous allez publier du code, testez-le ou au moins dites que vous ne l'avez pas fait.
Hugh Allen
1
Où? Soulignez-le et je vais le réparer. Je l'ai testé et cela a bien fonctionné sur les tableaux de taille paire et impaire.
dagorym
2
c'est une belle solution. L'esprit peut effectuer de tels exploits s'il est réglé à des fins. de O (n2) à O (1)
MoveFast
2
Ce n'est pas O (1); c'est toujours O (n ^ 2)
douma
11
Son O (n ^ 2) avec la mémoire O (1).
Neel
38

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]
peaufiner
la source
qu'est-ce que cela signifie "à mi-chemin du bord"? Je vois beaucoup d'algorithmes en boucle jusqu'à N / 2 et d'autres en boucle jusqu'à N, mais je ne vois pas d'où vient le N / 2.
PDN
Je crois que c'est la même solution que celle donnée dans le crack de l'interview de codage. Mais j'aime l'explication étape par étape. Très agréable et complet.
Naphstor
@PDN Cette réponse l' explique en détail.
Mathias Bynens
35

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.

Skizz
la source
4
Bravo! C'est une très bonne solution et je ne sais pas pourquoi ce n'est pas la réponse acceptée.
martinatime le
@martinatime: peut-être parce qu'il est 5 fois plus gros
Toad
@Toad: Eh bien, l'écriture de code est toujours un compromis entre des exigences concurrentes: vitesse, taille, coût, etc.
Skizz
15
vrai ... un autre problème est le fait que la matrice n'est en fait pas tournée, mais est tournée "juste à temps". Ce qui est idéal pour accéder à quelques éléments, mais serait horrible si cette matrice était utilisée dans des calculs ou des manipulations d'images. Donc, dire O (1) n'est pas vraiment juste.
Crapaud
23

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!

Drew Noakes
la source
1
+1 ... Et si la matrice est vraiment grande et que vous n'accédez qu'à quelques éléments (utilisation clairsemée), c'est encore plus efficace
lothar
16
Il semble un peu injuste d'appeler cela une solution de temps O (1). Pour résoudre le problème posé par l'OP, cela prendra encore O (n ^ 2). Non seulement cela, il ne résoudrait pas le problème car il renvoie la transposition . L'exemple donné n'a pas la transposition comme solution.
Vlad l'Impala
5
Maintenant, si tout ce que vous vouliez était les 3 premiers éléments de la matrice, c'est une bonne solution, mais le problème est de récupérer une matrice complètement transformée (c'est-à-dire en supposant que vous avez besoin de tous les éléments de la matrice). Appeler cet O (1) est la méthode Credit Default Swap d'analyse d'algorithmes - vous n'avez pas résolu le problème, vous venez de le pousser à quelqu'un d'autre :)
Ana Betts
4
@ Paul Betts: Je comprends votre argument, mais comme je l'ai écrit ci-dessus dans les commentaires, même si vous avez réellement la matrice transposée, vous devez toujours écrire la boucle si vous voulez lire les valeurs. La lecture de toutes les valeurs d'une matrice est donc toujours O (N ^ 2). La différence ici est que si vous transposez, faites pivoter, redimensionnez, redimensionnez, etc., alors vous ne prenez toujours le coup O (N ^ 2) qu'une seule fois. Comme je l'ai dit, ce n'est pas toujours la meilleure solution, mais dans de nombreux cas, c'est approprié et utile. L'OP semblait chercher une solution magique, et c'est aussi proche que possible.
Drew Noakes
9
J'aime cette réponse, mais je veux souligner quelque chose. L'impression de la matrice décorée (et l'exécution d'autres lectures séquentielles en général) peut être beaucoup plus lente que la même chose pour une matrice qui a été tournée en mémoire, et ce n'est pas uniquement à cause des appels de méthode virtuelle. Pour une grande matrice, vous allez augmenter considérablement le nombre de ratés de cache que vous obtenez en lisant "vers le bas" plutôt que "à travers".
Mike Daniels
18

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.

Martijn Courteaux
la source
Merci. C'était le code Java le plus clair ici. Question - Comment vous / Nick avez-vous conçu la partie [w-j-1]? En regardant la réponse @tweaking, je peux voir comment vous pourriez en tirer des exemples d'induction / résolution. Je me demande simplement si c'est comment il a été obtenu ou s'il est basé sur un principe mathématique relatif aux matrices.
Quest Monger
17

Ruby-way: .transpose.map &:reverse

Nakilon
la source
1
C'est encore plus simple que cela: array.reverse.transposefait pivoter un tableau dans le sens horaire, tout en le faisant array.transpose.reversetourner dans le sens antihoraire. Ce n'est pas nécessaire map.
Giorgi Gzirishvili
13

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.

Jason Oster
la source
Cependant, aucun de ceux-ci n'a pivoté à partir du tableau d'origine. Le premier, le résultat final est simplement transposé. Le second, vous semblez avoir simplement mélangé les lignes ou reflété à travers le centre horizontal. Le troisième, vous n'avez inversé que les lignes et le quatrième est également transposé. Aucun d'entre eux n'a en fait été "tourné".
SM177Y
Il y a quelques bugs dans les deux derniers exemples. Trivial à corriger. J'ai souligné explicitement que cette solution n'est pas une rotation sur place. C'est une fonction de transformation, ce qui la rend adaptée à l'itération paresseuse.
Jason Oster
Sauf qu'il n'y a pas de rotation, vous n'avez donc pas vraiment répondu à ce que le PO demandait.
SM177Y
@ SM177Y Un autre éditeur a ajouté un exemple de code non fonctionnel à ma réponse. Je peux voir à quel point cela vous a dérouté. J'ai corrigé les bugs dans les boucles d'itération. Les fonctions fournies permettent en fait de «faire pivoter» les données dans les tableaux.
Jason Oster
Un détail également important est que l'exemple de code efface vraiment la réponse originale que j'ai fournie, qui essayait d'illustrer la puissance des transformations fonctionnelles sur les solutions de complexité linéaire dans l'espace-temps. Avec une transformation fonctionnelle, vous êtes déjà en train d'itérer ou d'accéder autrement aux éléments du tableau , de sorte que la transformation est considérée comme «libre» dans le sens d'une complexité spatiale et temporelle constante.
Jason Oster
10

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.

nsanders
la source
Je suis d'accord avec ça. Avoir une méthode qui détermine la traduction entre les données source et les données "tournées".
martinatime le
8

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.

Kevin Berridge
la source
6

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;
        }
    }
}
2793692
la source
Ce n'est pas O (1). C'est O (n).
Jason Oster du
@JasonOster Je crois que c'est de l'espace O (1), car il ne consomme pas d'espace supplémentaire.
ffledgling
@ffledgling Mon erreur. O (1) complexité de l'espace, oui. O (n) complexité temporelle.
Jason Oster
La complexité spatiale est également O (n). La complexité de l'espace doit inclure l'espace de taille variable d'entrée. careercup.com/question?id=14952322
Jason Heo
Comment est-ce que je pourrais modifier ceci pour fonctionner pour une rotation antihoraire?
MD XF
5

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
Mike Stone
la source
4

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;
}
James Yu
la source
3

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;
}
mhawksey
la source
3

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 
Prateek Joshi
la source
2

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;
        }
    }
}
Spidey
la source
2

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.

radium
la source
2

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);
        }
    }
}
M. Nex
la source
2

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
ustmaestro
la source
2

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]
]
James Lin
la source
1

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.

Turc
la source
1

#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)

k00ka
la source
1

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;
        }
    }
}
rohitmb
la source
1

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;
        }
    }
}
thiagoh
la source
1

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;
}
user1596193
la source
1

@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
Nathan Fritz
la source
1
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.

William
la source
Parmi toutes ces réponses, j'ai trouvé et testé celle-ci qui est compacte et assez pour tourner
dlewin