Ich möchte noch ein wenig mehr Details hinzufügen. In dieser Antwort werden Schlüsselbegriffe wiederholt, das Tempo ist langsam und absichtlich repetitiv. Die hier angebotene Lösung ist nicht die syntaktisch kompakteste, sie ist jedoch für diejenigen gedacht, die lernen wollen, was eine Matrixrotation ist und wie sie umgesetzt wird.
Erstens: Was ist eine Matrix? Für die Zwecke dieser Antwort ist eine Matrix einfach ein Gitter, bei dem die Breite und die Höhe gleich sind. Beachten Sie, dass die Breite und Höhe einer Matrix unterschiedlich sein können, aber der Einfachheit halber werden in diesem Lernprogramm nur Matrizen mit gleicher Breite und Höhe betrachtet ( quadratische Matrizen ). Und ja, Matrizen ist der Plural von Matrix.
Beispielmatrizen sind: 2×2, 3×3 oder 5×5. Oder, allgemeiner ausgedrückt, N×N. Eine 2×2-Matrix hat 4 Quadrate, weil 2×2=4 ist. Eine 5×5-Matrix hat 25 Quadrate, weil 5×5=25. Jedes Quadrat wird als Element oder Eintrag bezeichnet. Wir stellen jedes Element mit einem Punkt dar ( . ) in den unten stehenden Diagrammen:
2×2-Matrix
. .
. .
3×3-Matrix
. . .
. . .
. . .
4×4-Matrix
. . . .
. . . .
. . . .
. . . .
Was bedeutet es also, eine Matrix zu drehen? Nehmen wir eine 2×2-Matrix und setzen wir einige Zahlen in jedes Element, damit die Drehung beobachtet werden kann:
0 1
2 3
Dreht man dies um 90 Grad, erhält man:
2 0
3 1
Wir haben die gesamte Matrix buchstäblich einmal nach rechts gedreht, so wie man das Lenkrad eines Autos dreht. Es kann hilfreich sein, sich vorzustellen, dass man die Matrix auf die rechte Seite "kippt". Wir wollen eine Funktion in Python schreiben, die eine Matrix nimmt und sie einmal nach rechts dreht. Die Funktionssignatur wird sein:
def rotate(matrix):
# Algorithm goes here.
Die Matrix wird über ein zweidimensionales Array definiert:
matrix = [
[0,1],
[2,3]
]
Daher greift die erste Indexposition auf die Zeile zu. Die zweite Indexposition greift auf die Spalte zu:
matrix[row][column]
Wir definieren eine Hilfsfunktion zum Drucken einer Matrix.
def print_matrix(matrix):
for row in matrix:
print row
Eine Methode zum Drehen einer Matrix besteht darin, eine Ebene nach der anderen zu bearbeiten. Aber was ist eine Ebene? Denken Sie an eine Zwiebel. Genau wie bei den Schichten einer Zwiebel bewegen wir uns mit jeder entfernten Schicht auf das Zentrum zu. Eine andere Analogie ist eine Matrjoschka-Puppe oder ein Spiel, bei dem das Paket weitergegeben wird.
Die Breite und Höhe einer Matrix bestimmen die Anzahl der Schichten in dieser Matrix. Verwenden wir für jede Ebene unterschiedliche Symbole:
Eine 2×2-Matrix hat 1 Schicht
. .
. .
Eine 3×3-Matrix hat 2 Schichten
. . .
. x .
. . .
Eine 4×4-Matrix hat 2 Schichten
. . . .
. x x .
. x x .
. . . .
Eine 5×5-Matrix hat 3 Schichten
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Eine 6×6-Matrix hat 3 Schichten
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
Eine 7×7-Matrix hat 4 Schichten
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
Sie werden feststellen, dass das Erhöhen der Breite und Höhe einer Matrix um eins nicht immer die Anzahl der Ebenen erhöht. Nimmt man die obigen Matrizen und tabelliert die Ebenen und Dimensionen, so stellt man fest, dass sich die Anzahl der Ebenen bei jeder zweimaligen Erhöhung von Breite und Höhe einmal erhöht:
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
Es müssen jedoch nicht alle Ebenen gedreht werden. Eine 1×1-Matrix ist vor und nach der Drehung die gleiche. Die zentrale 1×1-Schicht ist vor und nach der Drehung immer gleich groß, egal wie groß die Gesamtmatrix ist:
+-----+--------+------------------+
| 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 |
+-----+--------+------------------+
Wie kann man bei einer N×N-Matrix programmatisch die Anzahl der zu drehenden Ebenen bestimmen? Wenn wir die Breite oder Höhe durch zwei teilen und den Rest ignorieren, erhalten wir die folgenden Ergebnisse.
+-----+--------+------------------+---------+
| 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 |
+-----+--------+------------------+---------+
Beachten Sie, wie N/2 mit der Anzahl der Ebenen übereinstimmt, die gedreht werden müssen? Manchmal ist die Anzahl der drehbaren Ebenen eine weniger als die Gesamtzahl der Ebenen in der Matrix. Dies ist der Fall, wenn die innerste Schicht nur aus einem Element besteht (d. h. eine 1×1-Matrix) und daher nicht gedreht werden muss. Sie wird einfach ignoriert.
Wir werden diese Information zweifellos in unserer Funktion zum Drehen einer Matrix benötigen, also fügen wir sie jetzt hinzu:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
Jetzt wissen wir, was Ebenen sind und wie wir die Anzahl der Ebenen bestimmen, die tatsächlich gedreht werden müssen. Wie isolieren wir eine einzelne Ebene, damit wir sie drehen können? Zunächst untersuchen wir eine Matrix von der äußersten Schicht nach innen bis zur innersten Schicht. Eine 5×5-Matrix hat insgesamt drei Schichten und zwei Schichten, die gedreht werden müssen:
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Betrachten wir zunächst die Spalten. Die Position der Spalten, die die äußerste Schicht definieren, sind, wenn wir von 0 aus zählen, 0 und 4:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 und 4 sind auch die Positionen der Zeilen für die äußerste Schicht.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Dies wird immer der Fall sein, da die Breite und die Höhe gleich sind. Daher können wir die Spalten- und Zeilenpositionen einer Ebene mit nur zwei Werten (statt vier) definieren.
Auf der zweiten Ebene befinden sich die Spalten 1 und 3. Und, ja, Sie haben es erraten, das Gleiche gilt für die Zeilen. Es ist wichtig zu verstehen, dass wir die Zeilen- und Spaltenpositionen sowohl inkrementieren als auch dekrementieren müssen, wenn wir uns in die nächste Ebene bewegen.
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
Um also jede Schicht zu untersuchen, brauchen wir eine Schleife mit aufsteigenden und absteigenden Zählern, die sich von der äußersten Schicht aus nach innen bewegen. Wir nennen dies unsere "Schichtschleife".
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)
Der obige Code durchläuft in einer Schleife die (Zeilen- und Spalten-) Positionen aller Ebenen, die gedreht werden müssen.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
Wir haben jetzt eine Schleife, die die Positionen der Zeilen und Spalten jeder Ebene liefert. Die Variablen first y last die Indexposition der ersten und letzten Zeile und Spalte bestimmen. Beziehen Sie sich auf unsere Zeilen- und Spaltentabellen:
+--------+-----------+
| 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 | . . . . . |
+-----+-----------+
So können wir durch die Schichten einer Matrix navigieren. Jetzt brauchen wir eine Möglichkeit, innerhalb einer Ebene zu navigieren, damit wir Elemente in dieser Ebene verschieben können. Beachten Sie, dass Elemente niemals von einer Ebene zur anderen "springen", sondern sich innerhalb ihrer jeweiligen Ebene bewegen.
Durch Drehen der einzelnen Elemente in einer Ebene wird die gesamte Ebene gedreht. Wenn Sie alle Ebenen einer Matrix drehen, wird die gesamte Matrix gedreht. Dieser Satz ist sehr wichtig, also versuchen Sie bitte, ihn zu verstehen, bevor Sie fortfahren.
Jetzt brauchen wir eine Möglichkeit, die Elemente tatsächlich zu verschieben, d. h. jedes Element zu drehen, und anschließend die Ebene und schließlich die Matrix. Der Einfachheit halber werden wir auf eine 3x3-Matrix zurückgreifen - mit einer drehbaren Ebene.
0 1 2
3 4 5
6 7 8
Unsere Ebenenschleife liefert die Indizes der ersten und letzten Spalte sowie der ersten und letzten Zeile:
+-----+-------+
| 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 |
+-----+-------+
Da unsere Matrizen immer quadratisch sind, benötigen wir nur zwei Variablen, first y last , da die Indexpositionen für Zeilen und Spalten gleich sind.
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.
Die Variablen "first" und "last" können leicht verwendet werden, um auf die vier Ecken einer Matrix zu verweisen. Dies liegt daran, dass die Ecken selbst durch verschiedene Permutationen von first y last (ohne Subtraktion, Addition oder Offset dieser Variablen):
+---------------+-------------------+-------------+
| 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) |
+---------------+-------------------+-------------+
Aus diesem Grund beginnen wir mit der Rotation an den äußeren vier Ecken - wir werden diese zuerst drehen. Markieren wir sie mit * .
* 1 *
3 4 5
* 7 *
Wir wollen die einzelnen * mit dem * rechts daneben. Lassen Sie uns also unsere Ecken ausdrucken, die nur mit verschiedenen Permutationen von first y 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)
Die Ausgabe sollte sein:
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
Jetzt können wir ganz einfach jede der Ecken innerhalb unserer Ebenenschleife austauschen:
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)
Matrix vor dem Drehen der Ecken:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
Matrix nach dem Drehen der Ecken:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
Großartig! Wir haben erfolgreich jede Ecke der Matrix gedreht. Aber wir haben die Elemente in der Mitte jeder Ebene nicht gedreht. Es ist klar, dass wir eine Möglichkeit brauchen, innerhalb einer Ebene zu iterieren.
Das Problem ist, dass die einzige Schleife in unserer Funktion bisher (unsere Ebenenschleife) bei jeder Iteration zur nächsten Ebene wechselt. Da unsere Matrix nur eine drehbare Ebene hat, wird die Ebenenschleife nach dem Drehen nur der Ecken beendet. Schauen wir uns an, was mit einer größeren 5×5-Matrix passiert (bei der zwei Ebenen gedreht werden müssen). Der Funktionscode wurde weggelassen, aber er bleibt derselbe wie oben:
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)
Die Ausgabe ist:
[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]
Es sollte nicht überraschen, dass die Ecken der äußersten Schicht gedreht wurden, aber Sie können auch feststellen, dass die Ecken der nächsten Schicht (nach innen) ebenfalls gedreht wurden. Das macht Sinn. Wir haben Code geschrieben, um durch die Ebenen zu navigieren und auch die Ecken der einzelnen Ebenen zu drehen. Das fühlt sich wie ein Fortschritt an, aber leider müssen wir einen Schritt zurück machen. Es ist einfach nicht sinnvoll, zur nächsten Ebene überzugehen, bevor die vorherige (äußere) Ebene nicht vollständig gedreht wurde. Das heißt, bis jedes Element in der Ebene gedreht worden ist. Nur die Ecken zu drehen, reicht nicht aus!
Atmen Sie tief durch. Wir brauchen eine weitere Schleife. Und zwar eine verschachtelte Schleife. Die neue, verschachtelte Schleife verwendet die first y last Variablen sowie einen Offset, um innerhalb einer Ebene zu navigieren. Wir nennen diese neue Schleife unsere "Elementschleife". Die Elementschleife besucht jedes Element in der oberen Zeile, jedes Element auf der rechten Seite, jedes Element in der unteren Zeile und jedes Element auf der linken Seite.
- Um sich in der obersten Zeile vorwärts zu bewegen, muss die Spalte Index inkrementiert werden.
- Um auf der rechten Seite nach unten zu gelangen, muss der Zeilenindex inkrementiert werden.
- Die Rückwärtsbewegung entlang des Bodens erfordert die Spalte Index dekrementiert werden.
- Um auf der linken Seite nach oben zu gelangen, muss der Zeilenindex dekrementiert werden.
Das hört sich kompliziert an, ist aber ganz einfach, weil die Anzahl der Inkremente und Dekremente auf allen vier Seiten der Matrix gleich bleibt. Zum Beispiel:
- Verschieben Sie 1 Element in der obersten Reihe.
- Bewege 1 Element auf der rechten Seite nach unten.
- Verschiebe 1 Element in der unteren Reihe nach hinten.
- Bewege 1 Element auf der linken Seite nach oben.
Das bedeutet, dass wir eine einzelne Variable in Kombination mit dem first y last Variablen innerhalb einer Ebene zu verschieben. Es ist hilfreich zu wissen, dass die Bewegung über die oberste Reihe und die Bewegung nach unten auf der rechten Seite jeweils eine Inkrementierung erfordert. Wenn Sie sich rückwärts entlang der unteren Reihe und auf der linken Seite nach oben bewegen, müssen Sie beide dekrementieren.
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 = (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)
Jetzt müssen wir nur noch die Oberseite der rechten Seite, die rechte Seite der Unterseite, die Unterseite der linken Seite und die linke Seite der Oberseite zuordnen. Wenn wir das alles zusammenfügen, erhalten wir:
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
Gegeben die Matrix:
0, 1, 2
3, 4, 5
6, 7, 8
Unser rotate Funktion führt zu:
6, 3, 0
7, 4, 1
8, 5, 2
