Как вы вращаете двумерный массив?

Вдохновленный постом Рэймонда Чена, скажем, у вас есть двумерный массив 4x4, напишите функцию, которая поворачивает его на 90 градусов. Раймонд ссылается на решение в псевдокоде, но я хотел бы увидеть некоторые реальные вещи.

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

становится:

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

Обновление: ответ Ника самый простой, но есть ли способ сделать это лучше, чем n^2? Что делать, если матрица была 10000x10000?

64 ответа

Решение

Вот это в 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;
}

O(n^2) время и O(1) пространственный алгоритм (без каких-либо обходных путей и ханки-панки!)

Повернуть на +90:

  1. транспонировать
  2. Переверните каждый ряд

Повернуть на -90:

Способ 1:

  1. транспонировать
  2. Переверните каждый столбец

Способ 2:

  1. Переверните каждый ряд
  2. транспонировать

Повернуть на +180:

Метод 1: Поворот на +90 дважды

Метод 2: Переверните каждую строку и затем переверните каждый столбец (Транспонировать)

Повернуть на -180:

Метод 1: Поворот на -90 дважды

Способ 2: обратный каждый столбец, а затем обратный каждой строки

Способ 3: повернуть на +180, так как они одинаковые

Я хотел бы добавить немного больше деталей. В этом ответе ключевые понятия повторяются, темп медленный и намеренно повторяющийся. Представленное здесь решение не является наиболее синтаксически компактным, однако оно предназначено для тех, кто хочет узнать, что такое поворот матрицы и какова ее реализация.

Во-первых, что такое матрица? Для целей этого ответа матрица - это просто сетка, в которой ширина и высота одинаковы. Обратите внимание, что ширина и высота матрицы могут быть разными, но для простоты в этом руководстве рассматриваются только матрицы с одинаковой шириной и высотой (квадратные матрицы). И да, матрицы - это множественное число от матрицы.

Примеры матриц: 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  

Python:

rotated = zip(*original[::-1])  # On Python 3, list(zip(*original[::-1]))

Дешево, я знаю.

И против часовой стрелки:

rotated_ccw = zip(*original)[::-1]  # On Python 3, list(zip(*original))[::-1]

Как это работает: (запрошено в комментариях)

zip(*original) поменяет оси двумерных массивов, сложив соответствующие элементы из списков в новые списки. (The * оператор сообщает функции распределить содержащиеся списки в аргументы)

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

[::-1] Оператор обращает элементы массива (см. раздел "Расширенные фрагменты").

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

Наконец, объединение двух приведет к преобразованию вращения.

Изменение в размещении [::-1] перевернет списки на разных уровнях матрицы.

Вот тот, который выполняет вращение на месте, вместо того, чтобы использовать совершенно новый массив для хранения результата. Я прекратил инициализацию массива и распечатал его. Это работает только для квадратных массивов, но они могут быть любого размера. Накладные расходы памяти равны размеру одного элемента массива, поэтому вы можете вращать массив настолько, насколько вам нужно.

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;
    }
}

Здесь есть тонны хорошего кода, но я просто хочу показать, что происходит геометрически, чтобы вы могли немного лучше понять логику кода. Вот как я бы подошел к этому.

Прежде всего, не путайте это с транспозицией, которая очень проста..

Основная идея состоит в том, чтобы рассматривать его как слои, и мы вращаем один слой за раз.

скажем, у нас есть 4x4

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

после того, как мы повернем его по часовой стрелке на 90, мы получим

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

так что давайте разложим это, сначала мы вращаем 4 угла по существу

1           4


13          16

затем мы вращаем следующий алмаз, который является своего рода искривленным

    2
            8
9       
        15

а затем 2-й скошенный бриллиант

        3
5           
            12
    14

так что заботится о внешнем крае так по существу, мы делаем это по одной оболочке за раз, пока

наконец, средний квадрат (или, если он нечетный, только последний элемент, который не двигается)

6   7
10  11

так что теперь давайте выясним индексы каждого слоя, предположим, что мы всегда работаем с внешним слоем, мы делаем

[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]

так и так далее, пока мы не на полпути через край

так что в целом картина

[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]

Как я уже говорил в моем предыдущем посте, вот некоторый код на C#, который реализует поворот матрицы O(1) для матрицы любого размера. Для краткости и читабельности нет проверки ошибок или проверки диапазона. Код:

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;
}

Хорошо, я подниму руку, на самом деле при повороте он не вносит никаких изменений в исходный массив. Но в ОО-системе это не имеет значения, если объект выглядит так, как будто он был повернут для клиентов класса. На данный момент класс Matrix использует ссылки на исходные данные массива, поэтому изменение любого значения m1 также изменит m2 и m3. Небольшое изменение в конструкторе для создания нового массива и копирования значений в него позволит разобраться в этом.

Хотя вращение данных на месте может быть необходимым (возможно, для обновления физически сохраненного представления), становится проще и, возможно, более производительным добавить слой косвенности к доступу к массиву, возможно, к интерфейсу:

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

Если твой Matrix уже реализует этот интерфейс, его можно повернуть через класс декоратора, например так:

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);
    }
}

Поворот на +90/-90/180 градусов, переворачивание по горизонтали / вертикали и масштабирование - все это также может быть достигнуто.

Производительность должна быть измерена в вашем конкретном сценарии. Однако операция O(n^2) теперь заменена вызовом O(1). Это вызов виртуального метода, который медленнее, чем прямой доступ к массиву, поэтому он зависит от того, как часто повернутый массив используется после поворота. Если он используется один раз, то этот подход определенно победит. Если он вращается, а затем используется в длительной системе в течение нескольких дней, то вращение на месте может работать лучше. Это также зависит от того, можете ли вы принять предварительную стоимость.

Как и во всех вопросах производительности, измерять, измерять, измерять!

Это лучшая версия на Java: я сделал это для матрицы с другой шириной и высотой

  • h здесь высота матрицы после вращения
  • w здесь ширина матрицы после вращения

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;
}

Этот код основан на посте Ника Берарди.

Рубин-путь: .transpose.map &:reverse

Ответов уже много, и я нашел два, требующих O(1) временной сложности. Настоящий алгоритм O(1) состоит в том, чтобы оставить хранилище массива нетронутым и изменить способ индексации его элементов. Цель в том, что он не потребляет дополнительную память и не требует дополнительного времени для итерации данных.

Повороты на 90, -90 и 180 градусов - это простые преобразования, которые можно выполнять, если вы знаете, сколько строк и столбцов в вашем 2D-массиве; Чтобы повернуть любой вектор на 90 градусов, поменяйте местами оси и отрицайте ось Y. Для -90 градусов поменяйте местами оси и отрицайте ось X. При повороте на 180 градусов обе оси не меняются местами.

Возможны дальнейшие преобразования, такие как зеркальное отражение по горизонтали и / или по вертикали путем независимого отрицания осей.

Это можно сделать, например, с помощью метода доступа. Приведенные ниже примеры являются функциями JavaScript, но концепции в равной степени применимы ко всем языкам.

 // 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.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr.length; i++) {
  for (var j = 0; j < newarr[0].length; j++) {
    newarr[i][j] = 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.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr.length; i++) {
  for (var j = 0; j < newarr[0].length; j++) {
    newarr[i][j] = 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[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] = getArray2d180(arr, i, j);
  }
}
console.log(newarr);

Этот код предполагает наличие массива вложенных массивов, где каждый внутренний массив представляет собой строку.

Метод позволяет читать (или записывать) элементы (даже в случайном порядке), как если бы массив был повернут или преобразован. Теперь просто выберите правильную функцию для вызова, вероятно, по ссылке, и все готово!

Концепция может быть расширена для применения преобразований аддитивно (и неразрушающе) через методы доступа. В том числе произвольные углы поворота и масштабирования.

Несколько человек уже представили примеры, которые включают создание нового массива.

Несколько других вещей, чтобы рассмотреть:

(а) Вместо того, чтобы на самом деле перемещать данные, просто перемещайтесь по "повернутому" массиву по-другому.

(б) Выполнение вращения на месте может быть немного сложнее. Вам понадобится немного места для царапин (вероятно, примерно равного одному размеру строки или столбца). Есть древняя статья ACM о выполнении транспонирования на месте ( http://doi.acm.org/10.1145/355719.355729), но их пример кода - это грязный готовый к загрузке фортран.

Приложение:

http://doi.acm.org/10.1145/355611.355612 - это еще один, предположительно, превосходный алгоритм транспонирования на месте.

Ответ Ника будет работать и для массива NxM с небольшой модификацией (в отличие от 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];

Один из способов думать об этом состоит в том, что вы переместили центр оси (0,0) из верхнего левого угла в верхний правый угол. Вы просто переносите из одного в другое.

Время - O(N), Пространство - 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;
        }
    }
}

Распространенный метод поворота 2D-массива по или против часовой стрелки.

  • по часовой стрелке вращать
    • сначала переверните вверх вниз, затем поменяйте местами симметрию
      1 2 3     7 8 9     7 4 1
      4 5 6  => 4 5 6  => 8 5 2
      7 8 9     1 2 3     9 6 3
      
void rotate(vector<vector<int> > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}
  • вращать против часовой стрелки
    • сначала перевернуть слева направо, затем поменять местами симметрию
      1 2 3     3 2 1     3 6 9
      4 5 6  => 6 5 4  => 2 5 8
      7 8 9     9 8 7     1 4 7
      
void anti_rotate(vector<vector<int> > &matrix) {
    for (auto vi : matrix) reverse(vi.begin(), vi.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

Вот моя версия Ruby (обратите внимание, что значения не отображаются одинаково, но они все еще вращаются, как описано).

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

Выход:

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

Вот метод поворота в пространстве, по Java, только для квадрата. для не квадратного 2d массива вам все равно придется создавать новый массив.

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;
            }
        }
    }
}

код для вращения любого размера 2d массива путем создания нового массива:

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;
}

Вы можете сделать это в 3 простых шага:

1) Предположим, у нас есть матрица

   1 2 3
   4 5 6
   7 8 9

2) Взять транспонирование матрицы

   1 4 7
   2 5 8
   3 6 9

3) чередуйте строки, чтобы получить повернутую матрицу

   3 6 9
   2 5 8
   1 4 7

Исходный кодJava для этого:

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();
        }
    }
}

Выход:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 

В питоне:

      import numpy as np

a = np.array(
    [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 0, 1, 2],
        [3, 4, 5, 6]
    ]
)

print(a)
print(b[::-1, :].T)

Реализация псевдокода +90 для dimple (например, транспонировать, затем перевернуть каждую строку) в 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;
}

Это моя реализация, в C, O(1) сложность памяти, поворот на месте, 90 градусов по часовой стрелке:

#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;
        }
    }
}

С линейной точки зрения рассмотрим матрицы:

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

Теперь возьми транспонирование

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

И рассмотрим действие A на B или B на A.
Соответственно:

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

Это расширяется для любой матрицы n x n. И быстро применить эту концепцию в коде:

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);
        }
    }
}

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);
    }
}
?>

Хорошие ответы, но для тех, кто ищет для этого СУХОЙ код JavaScript - и +90 градусов, и -90 градусов:

          // Input: 1 2 3
          //        4 5 6
          //        7 8 9

          // Transpose: 
          //       1 4 7
          //       2 5 8
          //       3 6 9

          // Output: 
          // +90 Degree:
          //       7 4 1
          //       8 5 2
          //       9 6 3

          // -90 Degree:
          //      3 6 9
          //      2 5 8
          //      1 4 7

          // Rotate +90
         function rotate90(matrix) {

           matrix = transpose(matrix);
           matrix.map(function(array) {
             array.reverse();
           });

           return matrix;
         }

          // Rotate -90
         function counterRotate90(matrix) {
           var result = createEmptyMatrix(matrix.length);
           matrix = transpose(matrix);
           var counter = 0;

           for (var i = matrix.length - 1; i >= 0; i--) {
             result[counter] = matrix[i];
             counter++;
           }

           return result;
         }

          // Create empty matrix
         function createEmptyMatrix(len) {
           var result = new Array();
           for (var i = 0; i < len; i++) {
             result.push([]);
           }
           return result;
         }

          // Transpose the matrix
         function transpose(matrix) {
           // make empty array
           var len = matrix.length;
           var result = createEmptyMatrix(len);

           for (var i = 0; i < matrix.length; i++) {
             for (var j = 0; j < matrix[i].length; j++) {
               var temp = matrix[i][j];
               result[j][i] = temp;
             }
           }
           return result;
         }



          // Test Cases
         var array1 = [
           [1, 2],
           [3, 4]
         ];
         var array2 = [
           [1, 2, 3],
           [4, 5, 6],
           [7, 8, 9]
         ];
         var array3 = [
           [1, 2, 3, 4],
           [5, 6, 7, 8],
           [9, 10, 11, 12],
           [13, 14, 15, 16]
         ];

          // +90 degress Rotation Tests

         var test1 = rotate90(array1);
         var test2 = rotate90(array2);
         var test3 = rotate90(array3);
         console.log(test1);
         console.log(test2);
         console.log(test3);

          // -90 degress Rotation Tests
         var test1 = counterRotate90(array1);
         var test2 = counterRotate90(array2);
         var test3 = counterRotate90(array3);
         console.log(test1);
         console.log(test2);
         console.log(test3);

Код C# для поворота [n,m] 2D-массивов на 90 градусов вправо

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();
        }
    }
}

Результат:

    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

Вот версия 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;
        }
    }
}

метод сначала вращает самый верхний слой, затем последовательно перемещается к внутреннему слою.

@dagorym: Ой, чувак. Я держался за это как хорошую головоломку "мне скучно, что я могу обдумать". Я придумал свой код транспонирования на месте, но попал сюда, чтобы найти ваш, в значительной степени идентичный моему... ах, хорошо. Вот это в 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

C-код для поворота матрицы на 90 градусов по часовой стрелке НА МЕСТЕ для любой матрицы 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;
        }
    }
}

Вот моя попытка поворота матрицы на 90 градусов, которая является двухшаговым решением в C. Сначала переставьте матрицу на месте, а затем поменяйте местами столбцы.

#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;
}

C-код для транспонирования и поворота матрицы (+/-90, +/-180)

  • Поддерживает квадратные и неквадратные матрицы, имеет встроенные функции и функции копирования
  • Поддерживает 2D-массивы и 1D-указатели с логическими строками / столбцами
  • Юнит-тесты; см тесты для примеров использования
  • проверено gcc -std=c90 -стена -педантика, MSVC17

`

#include <stdlib.h>
#include <memory.h>
#include <assert.h>

/* 
    Matrix transpose & rotate (+/-90, +/-180)
        Supports both 2D arrays and 1D pointers with logical rows/cols
        Supports square and non-square matrices, has in-place and copy features
        See tests for examples of usage
    tested gcc -std=c90 -Wall -pedantic, MSVC17
*/

typedef int matrix_data_t;  /* matrix data type */

void transpose(const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void transpose_inplace(matrix_data_t* data, int n );
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols);
void rotate_inplace(int direction, matrix_data_t* data, int n);
void reverse_rows(matrix_data_t* data, int rows, int cols);
void reverse_cols(matrix_data_t* data, int rows, int cols);

/* test/compare fn */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols );

/* TESTS/USAGE */
void transpose_test() {

    matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };/* 3x3 square, odd length side */
    matrix_data_t sq3x3_cpy[9];
    matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };/* 2D 3x3 square */
    matrix_data_t sq3x3_2D_copy[3][3];

    /* expected test values */
    const matrix_data_t sq3x3_orig[9] = { 0,1,2,3,4,5,6,7,8 };
    const matrix_data_t sq3x3_transposed[9] = { 0,3,6,1,4,7,2,5,8};

    matrix_data_t sq4x4[16]= { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };/* 4x4 square, even length*/
    const matrix_data_t sq4x4_orig[16] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
    const matrix_data_t sq4x4_transposed[16] = { 0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15 };

    /* 2x3 rectangle */
    const matrix_data_t r2x3_orig[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r2x3_transposed[6] = { 0,3,1,4,2,5 };
    matrix_data_t r2x3_copy[6];

    matrix_data_t r2x3_2D[2][3] = { {0,1,2},{3,4,5} };  /* 2x3 2D rectangle */
    matrix_data_t r2x3_2D_t[3][2];

    /* matrix_data_t r3x2[6] = { 0,1,2,3,4,5 }; */
    matrix_data_t r3x2_copy[6];
    /* 3x2 rectangle */
    const matrix_data_t r3x2_orig[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r3x2_transposed[6] = { 0,2,4,1,3,5 };

    matrix_data_t r6x1[6] = { 0,1,2,3,4,5 };    /* 6x1 */
    matrix_data_t r6x1_copy[6];

    matrix_data_t r1x1[1] = { 0 };  /*1x1*/
    matrix_data_t r1x1_copy[1];

    /* 3x3 tests, 2D array tests */
    transpose_inplace(sq3x3, 3);    /* transpose in place */
    assert(!test_cmp(sq3x3, sq3x3_transposed, 3, 3));
    transpose_inplace(sq3x3, 3);    /* transpose again */
    assert(!test_cmp(sq3x3, sq3x3_orig, 3, 3));

    transpose(sq3x3, sq3x3_cpy, 3, 3);  /* transpose copy 3x3*/
    assert(!test_cmp(sq3x3_cpy, sq3x3_transposed, 3, 3));

    transpose((matrix_data_t*)sq3x3_2D, (matrix_data_t*)sq3x3_2D_copy, 3, 3);   /* 2D array transpose/copy */
    assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_transposed, 3, 3));
    transpose_inplace((matrix_data_t*)sq3x3_2D_copy, 3);    /* 2D array transpose in place */
    assert(!test_cmp((matrix_data_t*)sq3x3_2D_copy, sq3x3_orig, 3, 3));

    /* 4x4 tests */
    transpose_inplace(sq4x4, 4);    /* transpose in place */
    assert(!test_cmp(sq4x4, sq4x4_transposed, 4,4));
    transpose_inplace(sq4x4, 4);    /* transpose again */
    assert(!test_cmp(sq4x4, sq4x4_orig, 3, 3));

    /* 2x3,3x2 tests */
    transpose(r2x3_orig, r2x3_copy, 2, 3);
    assert(!test_cmp(r2x3_copy, r2x3_transposed, 3, 2));

    transpose(r3x2_orig, r3x2_copy, 3, 2);
    assert(!test_cmp(r3x2_copy, r3x2_transposed, 2,3));

    /* 2D array */
    transpose((matrix_data_t*)r2x3_2D, (matrix_data_t*)r2x3_2D_t, 2, 3);
    assert(!test_cmp((matrix_data_t*)r2x3_2D_t, r2x3_transposed, 3,2));

    /* Nx1 test, 1x1 test */
    transpose(r6x1, r6x1_copy, 6, 1);
    assert(!test_cmp(r6x1_copy, r6x1, 1, 6));

    transpose(r1x1, r1x1_copy, 1, 1);
    assert(!test_cmp(r1x1_copy, r1x1, 1, 1));

}

void rotate_test() {

    /* 3x3 square */
    const matrix_data_t sq3x3[9] = { 0,1,2,3,4,5,6,7,8 };
    const matrix_data_t sq3x3_r90[9] = { 6,3,0,7,4,1,8,5,2 };
    const matrix_data_t sq3x3_180[9] = { 8,7,6,5,4,3,2,1,0 };
    const matrix_data_t sq3x3_l90[9] = { 2,5,8,1,4,7,0,3,6 };
    matrix_data_t sq3x3_copy[9];

    /* 3x3 square, 2D */
    matrix_data_t sq3x3_2D[3][3] = { { 0,1,2 },{ 3,4,5 },{ 6,7,8 } };

    /* 4x4, 2D */
    matrix_data_t sq4x4[4][4] = { { 0,1,2,3 },{ 4,5,6,7 },{ 8,9,10,11 },{ 12,13,14,15 } };
    matrix_data_t sq4x4_copy[4][4];
    const matrix_data_t sq4x4_r90[16] = { 12,8,4,0,13,9,5,1,14,10,6,2,15,11,7,3 };
    const matrix_data_t sq4x4_l90[16] = { 3,7,11,15,2,6,10,14,1,5,9,13,0,4,8,12 };
    const matrix_data_t sq4x4_180[16] = { 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 };

    matrix_data_t r6[6] = { 0,1,2,3,4,5 };  /* rectangle with area of 6 (1x6,2x3,3x2, or 6x1) */
    matrix_data_t r6_copy[6];
    const matrix_data_t r1x6_r90[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r1x6_l90[6] = { 5,4,3,2,1,0 };
    const matrix_data_t r1x6_180[6] = { 5,4,3,2,1,0 };

    const matrix_data_t r2x3_r90[6] = { 3,0,4,1,5,2 };
    const matrix_data_t r2x3_l90[6] = { 2,5,1,4,0,3 };
    const matrix_data_t r2x3_180[6] = { 5,4,3,2,1,0 };

    const matrix_data_t r3x2_r90[6] = { 4,2,0,5,3,1 };
    const matrix_data_t r3x2_l90[6] = { 1,3,5,0,2,4 };
    const matrix_data_t r3x2_180[6] = { 5,4,3,2,1,0 };

    const matrix_data_t r6x1_r90[6] = { 5,4,3,2,1,0 };
    const matrix_data_t r6x1_l90[6] = { 0,1,2,3,4,5 };
    const matrix_data_t r6x1_180[6] = { 5,4,3,2,1,0 };

    /* sq3x3 tests */
    rotate(90, sq3x3, sq3x3_copy, 3, 3);    /* +90 */
    assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
    rotate(-90, sq3x3, sq3x3_copy, 3, 3);   /* -90 */
    assert(!test_cmp(sq3x3_copy, sq3x3_l90, 3, 3));
    rotate(180, sq3x3, sq3x3_copy, 3, 3);   /* 180 */
    assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
    /* sq3x3 in-place rotations */
    memcpy( sq3x3_copy, sq3x3, 3 * 3 * sizeof(matrix_data_t));
    rotate_inplace(90, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3_r90, 3, 3));
    rotate_inplace(-90, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3)); /* back to 0 orientation */
    rotate_inplace(180, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3_180, 3, 3));
    rotate_inplace(-180, sq3x3_copy, 3);
    assert(!test_cmp(sq3x3_copy, sq3x3, 3, 3));
    rotate_inplace(180, (matrix_data_t*)sq3x3_2D, 3);/* 2D test */
    assert(!test_cmp((matrix_data_t*)sq3x3_2D, sq3x3_180, 3, 3));

    /* sq4x4 */
    rotate(90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
    assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_r90, 4, 4));
    rotate(-90, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
    assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_l90, 4, 4));
    rotate(180, (matrix_data_t*)sq4x4, (matrix_data_t*)sq4x4_copy, 4, 4);
    assert(!test_cmp((matrix_data_t*)sq4x4_copy, sq4x4_180, 4, 4));

    /* r6 as 1x6 */
    rotate(90, r6, r6_copy, 1, 6);
    assert(!test_cmp(r6_copy, r1x6_r90, 1, 6));
    rotate(-90, r6, r6_copy, 1, 6);
    assert(!test_cmp(r6_copy, r1x6_l90, 1, 6));
    rotate(180, r6, r6_copy, 1, 6);
    assert(!test_cmp(r6_copy, r1x6_180, 1, 6));

    /* r6 as 2x3 */
    rotate(90, r6, r6_copy, 2, 3);
    assert(!test_cmp(r6_copy, r2x3_r90, 2, 3));
    rotate(-90, r6, r6_copy, 2, 3);
    assert(!test_cmp(r6_copy, r2x3_l90, 2, 3));
    rotate(180, r6, r6_copy, 2, 3);
    assert(!test_cmp(r6_copy, r2x3_180, 2, 3));

    /* r6 as 3x2 */
    rotate(90, r6, r6_copy, 3, 2);
    assert(!test_cmp(r6_copy, r3x2_r90, 3, 2));
    rotate(-90, r6, r6_copy, 3, 2);
    assert(!test_cmp(r6_copy, r3x2_l90, 3, 2));
    rotate(180, r6, r6_copy, 3, 2);
    assert(!test_cmp(r6_copy, r3x2_180, 3, 2));

    /* r6 as 6x1 */
    rotate(90, r6, r6_copy, 6, 1);
    assert(!test_cmp(r6_copy, r6x1_r90, 6, 1));
    rotate(-90, r6, r6_copy, 6, 1);
    assert(!test_cmp(r6_copy, r6x1_l90, 6, 1));
    rotate(180, r6, r6_copy, 6, 1);
    assert(!test_cmp(r6_copy, r6x1_180, 6, 1));
}

/* test comparison fn, return 0 on match else non zero */
int test_cmp(const matrix_data_t* lhs, const matrix_data_t* rhs, int rows, int cols) {

    int r, c;

    for (r = 0; r < rows; ++r) {
        for (c = 0; c < cols; ++c) {
            if ((lhs + r * cols)[c] != (rhs + r * cols)[c])
                return -1;
        }
    }
    return 0;
}

/*
Reverse values in place of each row in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] ->  [C B A]
[D E F]     [F E D]
*/
void reverse_rows(matrix_data_t* data, int rows, int cols) {

    int r, c;
    matrix_data_t temp;
    matrix_data_t* pRow = NULL;

    for (r = 0; r < rows; ++r) {
        pRow = (data + r * cols);
        for (c = 0; c < (int)(cols / 2); ++c) { /* explicit truncate */
            temp = pRow[c];
            pRow[c] = pRow[cols - 1 - c];
            pRow[cols - 1 - c] = temp;
        }
    }
}

/*
Reverse values in place of each column in 2D matrix data[rows][cols] or in 1D pointer with logical rows/cols
[A B C] ->  [D E F]
[D E F]     [A B C]
*/
void reverse_cols(matrix_data_t* data, int rows, int cols) {

    int r, c;
    matrix_data_t temp;
    matrix_data_t* pRowA = NULL;
    matrix_data_t* pRowB = NULL;

    for (c = 0; c < cols; ++c) {
        for (r = 0; r < (int)(rows / 2); ++r) { /* explicit truncate */
            pRowA = data + r * cols;
            pRowB = data + cols * (rows - 1 - r);
            temp = pRowA[c];
            pRowA[c] = pRowB[c];
            pRowB[c] = temp;
        }
    }
}

/* Transpose NxM matrix to MxN matrix in O(n) time */
void transpose(const matrix_data_t* src, matrix_data_t* dst, int N, int M) {

    int i;
    for (i = 0; i<N*M; ++i) dst[(i%M)*N + (i / M)] = src[i];    /* one-liner version */

    /*
    expanded version of one-liner:  calculate XY based on array index, then convert that to YX array index
    int i,j,x,y;
    for (i = 0; i < N*M; ++i) {
    x = i % M;
    y = (int)(i / M);
    j = x * N + y;
    dst[j] = src[i];
    }
    */

    /*
    nested for loop version
    using ptr arithmetic to get proper row/column
    this is really just dst[col][row]=src[row][col]

    int r, c;

    for (r = 0; r < rows; ++r) {
        for (c = 0; c < cols; ++c) {
            (dst + c * rows)[r] = (src + r * cols)[c];
        }
    }
    */
}

/*
Transpose NxN matrix in place
*/
void transpose_inplace(matrix_data_t* data, int N ) {

    int r, c;
    matrix_data_t temp;

    for (r = 0; r < N; ++r) {
        for (c = r; c < N; ++c) { /*start at column=row*/
                                    /* using ptr arithmetic to get proper row/column */
                                    /* this is really just
                                    temp=dst[col][row];
                                    dst[col][row]=src[row][col];
                                    src[row][col]=temp;
                                    */
            temp = (data + c * N)[r];
            (data + c * N)[r] = (data + r * N)[c];
            (data + r * N)[c] = temp;
        }
    }
}

/*
Rotate 1D or 2D src matrix to dst matrix in a direction (90,180,-90)
Precondition:  src and dst are 2d matrices with dimensions src[rows][cols] and dst[cols][rows] or 1D pointers with logical rows/cols
*/
void rotate(int direction, const matrix_data_t* src, matrix_data_t* dst, int rows, int cols) {

    switch (direction) {
    case -90:
        transpose(src, dst, rows, cols);
        reverse_cols(dst, cols, rows);
        break;
    case 90:
        transpose(src, dst, rows, cols);
        reverse_rows(dst, cols, rows);
        break;
    case 180:
    case -180:
        /* bit copy to dst, use in-place reversals */
        memcpy(dst, src, rows*cols*sizeof(matrix_data_t));
        reverse_cols(dst, cols, rows);
        reverse_rows(dst, cols, rows);
        break;
    }
}

/*
Rotate array in a direction.
Array must be NxN 2D or 1D array with logical rows/cols
Direction can be (90,180,-90,-180)
*/
void rotate_inplace( int direction, matrix_data_t* data, int n) {

    switch (direction) {
    case -90:
        transpose_inplace(data, n);
        reverse_cols(data, n, n);
        break;
    case 90:
        transpose_inplace(data, n);
        reverse_rows(data, n, n);
        break;
    case 180:
    case -180:
        reverse_cols(data, n, n);
        reverse_rows(data, n, n);
        break;
    }
}

`

Другие вопросы по тегам