Я хотел бы добавить немного больше деталей. В этом ответе ключевые понятия повторяются, темп медленный и намеренно повторяющийся. Представленное здесь решение не является наиболее синтаксически компактным, однако оно предназначено для тех, кто хочет узнать, что такое поворот матрицы и какова ее реализация.
Во-первых, что такое матрица? Для целей этого ответа матрица - это просто сетка, в которой ширина и высота одинаковы. Обратите внимание, что ширина и высота матрицы могут быть разными, но для простоты в этом руководстве рассматриваются только матрицы с одинаковой шириной и высотой ( квадратные матрицы ). И да, матрицы - это множественное число матрицы.
Примеры матриц: 2 × 2, 3 × 3 или 5 × 5. Или, в более общем случае, N × N. Матрица 2 × 2 будет иметь 4 квадрата, потому что 2 × 2 = 4. Матрица 5 × 5 будет иметь 25 квадратов, потому что 5 × 5 = 25. Каждый квадрат называется элементом или записью. Мы представим каждый элемент с точкой (.) на диаграммах ниже:
2 × 2 матрицы
. .
. .
3 × 3 матрицы
. . .
. . .
. . .
матрица 4 × 4
. . . .
. . . .
. . . .
. . . .
Итак, что значит вращать матрицу? Давайте возьмем матрицу 2 × 2 и поместим несколько чисел в каждый элемент, чтобы можно было наблюдать вращение:
0 1
2 3
Поворот на 90 градусов дает нам:
2 0
3 1
Мы буквально повернули всю матрицу один раз вправо, точно так же, как поворачивали руль автомобиля. Это может помочь подумать о «опрокидывании» матрицы с правой стороны. Мы хотим написать функцию на Python, которая принимает матрицу и поворачивается один раз вправо. Подпись функции будет:
def rotate(matrix):
# Algorithm goes here.
Матрица будет определена с использованием двумерного массива:
matrix = [
[0,1],
[2,3]
]
Следовательно, первая позиция указателя обращается к строке. Вторая индексная позиция обращается к столбцу:
matrix[row][column]
Мы определим служебную функцию для печати матрицы.
def print_matrix(matrix):
for row in matrix:
print row
Один из способов поворота матрицы состоит в том, чтобы сделать ее слоем за раз. Но что такое слой? Подумай о луке. Так же, как слои лука, так как каждый слой удаляется, мы движемся к центру. Другие аналогии - это Матрешка или игра в посылку.
Ширина и высота матрицы определяют количество слоев в этой матрице. Давайте использовать разные символы для каждого слоя:
Матрица 2 × 2 имеет 1 слой
. .
. .
Матрица 3 × 3 имеет 2 слоя
. . .
. x .
. . .
Матрица 4 × 4 имеет 2 слоя
. . . .
. x x .
. x x .
. . . .
Матрица 5 × 5 имеет 3 слоя
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Матрица 6 × 6 имеет 3 слоя
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
Матрица 7 × 7 имеет 4 слоя
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
Вы можете заметить, что увеличение ширины и высоты матрицы на единицу не всегда увеличивает количество слоев. Взяв вышеприведенные матрицы и таблицы слоев и размеров, мы видим, что количество слоев увеличивается один раз на каждые два приращения ширины и высоты:
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
Однако не все слои нуждаются во вращении. Матрица 1 × 1 одинакова до и после вращения. Центральный слой 1 × 1 всегда одинаков до и после вращения, независимо от размера всей матрицы:
+-----+--------+------------------+
| 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 |
+-----+--------+------------------+
Учитывая матрицу N × N, как мы можем программно определить количество слоев, которые нам нужно повернуть? Если мы разделим ширину или высоту на два и проигнорируем остаток, мы получим следующие результаты.
+-----+--------+------------------+---------+
| 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 |
+-----+--------+------------------+---------+
Обратите внимание, как N/2 соответствует количеству слоев, которые необходимо повернуть? Иногда количество вращающихся слоев на единицу меньше общего количества слоев в матрице. Это происходит, когда самый внутренний слой сформирован только из одного элемента (то есть матрицы 1 × 1) и, следовательно, не нуждается во вращении. Это просто игнорируется.
Нам, несомненно, понадобится эта информация в нашей функции для вращения матрицы, поэтому давайте добавим ее сейчас:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
Теперь мы знаем, что такое слои иКак определить количество слоев, которые на самом деле нужно вращать, как мы изолируем один слой, чтобы мы могли вращать его? Во-первых, мы проверяем матрицу от самого внешнего слоя внутрь до самого внутреннего слоя. Матрица 5 × 5 имеет всего три слоя и два слоя, которые нужно вращать:
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Давайте сначала посмотрим на столбцы. Положение столбцов, определяющих самый внешний слой, при условии, что мы считаем от 0, равно 0 и 4:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 и 4 также являются позициями строк для самого внешнего слоя.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Это всегда будет так, поскольку ширина и высота одинаковы. Поэтому мы можем определить положение столбца и строки слоя только с двумя значениями (а не с четырьмя).
При перемещении внутрь ко второму слою позиции столбцов 1 и 3. И, как вы уже догадались, для строк то же самое. Важно понимать, что мы должны увеличивать и уменьшать позиции строк и столбцов при переходе внутрь к следующему слою.
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
Итак, для осмотра каждого слоя нам нужен цикл с увеличивающимися и уменьшающимися счетчиками, которые представляют собой движение внутрь, начиная с самого внешнего слоя. Мы назовем это нашей «петлей слоя».
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)
Приведенный выше код перебирает позиции (строки и столбцы) любых слоев, которые нужно вращать.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
Теперь у нас есть цикл, предоставляющий позиции строк и столбцов каждого слоя. Переменные first и last идентифицируют позицию индекса первой и последней строк и столбцов. Возвращаясь к нашим таблицам строк и столбцов:
+--------+-----------+
| 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 | . . . . . |
+-----+-----------+
Так что мы можем перемещаться по слоям матрицы. Теперь нам нужен способ навигации внутри слоя, чтобы мы могли перемещать элементы вокруг этого слоя. Обратите внимание, что элементы никогда не «перепрыгивают» с одного слоя на другой, но они перемещаются внутри соответствующих слоев.
Вращение каждого элемента в слое вращает весь слой. Вращение всех слоев в матрице вращает всю матрицу. Это предложение очень важно, поэтому, пожалуйста, постарайтесь понять его, прежде чем двигаться дальше.
Теперь нам нужен способ фактически перемещать элементы, то есть вращать каждый элемент, а затем слой и, в конечном итоге, матрицу. Для простоты мы вернемся к матрице 3х3 - с одним вращающимся слоем.
0 1 2
3 4 5
6 7 8
Наш цикл слоя предоставляет индексы первого и последнего столбцов, а также первой и последней строк:
+-----+-------+
| 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 |
+-----+-------+
Поскольку наши матрицы всегда квадратные, нам нужны только две переменные, first и last, поскольку позиции индекса одинаковы для строк и столбцов.
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.
Переменные first и last можно легко использовать для ссылки на четыре угла матрицы. Это происходит потому, что сами углы могут быть определены с использованием различных перестановок first и last (без вычитания, сложения или смещения этих переменных):
+---------------+-------------------+-------------+
| 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) |
+---------------+-------------------+-------------+
По этой причине мы начинаем наше вращение с внешних четырех углов - мы будем вращать их первыми. Давайте выделим их с помощью *.
* 1 *
3 4 5
* 7 *
Мы хотим поменять местами каждый * с * справа от него. Итак, давайте продолжим распечатывать наши углы, определенные только с использованием различных комбинаций first и 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)
Вывод должен быть:
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
Теперь мы можем довольно легко поменять каждый из углов внутри нашего цикла слоя:
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)
Матрица перед поворотом углов:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
Матрица после поворота углов:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
Отлично! Мы успешно повернули каждый угол матрицы. Но мы не вращали элементы в середине каждого слоя. Ясно, что нам нужен способ итерации внутри слоя.
Проблема только в том,пока что цикл в нашей функции (наш цикл слоя) переходит к следующему слою на каждой итерации. Поскольку наша матрица имеет только один вращающийся слой, петля слоя выходит после поворота только углов. Давайте посмотрим, что происходит с более крупной матрицей 5 × 5 (где два слоя нужно вращать). Код функции был опущен, но он остается таким же, как указано выше:
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)
Вывод:
[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]
Не должно быть сюрпризом, что углы внешнего слоя были повернуты, но вы также можете заметить, что углы следующего слоя (внутрь) также были повернуты. Это имеет смысл. Мы написали код для навигации по слоям, а также для поворота углов каждого слоя. Это похоже на прогресс, но, к сожалению, мы должны сделать шаг назад. Просто переходить к следующему слою бесполезно, пока предыдущий (внешний) слой не будет полностью повернут. То есть, пока каждый элемент в слое не будет повернут. Вращать только углы не получится!
Сделайте глубокий вдох. Нам нужен еще один цикл. Вложенный цикл не меньше. Новый вложенный цикл будет использовать переменные first и last, а также смещение для навигации по слою. Мы назовем этот новый цикл нашим «элементным циклом». Цикл элементов будет посещать каждый элемент в верхнем ряду, каждый элемент в правой части, каждый элемент в нижнем ряду и каждый элемент в левой части.
- Для продвижения вперед по верхнему ряду необходим столбец
индекс для увеличения.
- Перемещение вниз по правой стороне требует, чтобы индекс строки был
увеличивается.
- Для движения назад по дну необходим столбец
Индекс должен быть уменьшен.
- Для перемещения вверх по левой стороне необходим индекс строки
убавления.
Это звучит сложно, но это легко сделать, потому что количество раз, которое мы увеличиваем и уменьшаем для достижения вышеуказанного, остается одинаковым по всем четырем сторонам матрицы. Например:
- Переместить 1 элемент по верхнему ряду.
- Переместить 1 элемент вниз по правой стороне.
- Переместить 1 элемент назад вдоль нижнего ряда.
- Переместить 1 элемент вверх по левой стороне.
Это означает, что мы можем использовать одну переменную в сочетании с переменными first и last для перемещения внутри слоя. Это может помочь заметить, что перемещение по верхнему ряду и вниз по правой стороне требует увеличения. При движении назад вдоль нижней и левой стороны оба требуют уменьшения.
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)
Теперь нам просто нужно присвоить верхнюю часть правой стороне, правую сторону нижней части, нижнюю часть левой стороне и левую сторону верхней части. Собрав все это вместе, мы получим:
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
С учетом матрицы:
0, 1, 2
3, 4, 5
6, 7, 8
Наша функция rotate приводит к:
6, 3, 0
7, 4, 1
8, 5, 2