Вращение на месте одномерного представления квадратной матрицы nxn

Question

У меня есть матрица n x n, представленная в виде 1-D массива.Верхний левый угол начинается с индекса 0. Индекс i вычисляется как i = x * n + y, где x и y - индексы матричной записи в двумерном представлении.

Для n = 4

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

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

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

Отображение теперь i = 12 + y - (n * x)

Используя O (n ^ 2) пространство, мы просто отображаем оригиналиндекс на повернутый индекс и скопировать запись в исходное положение.Очень просто.

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

Answer 1

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

Так, например, для поворота на 90 градусов, первое отражение можно сделать вокруг оси x, поменяв местами первый ряд с последним рядом, а затем поменяв местами второй ряд св третьей строке вы получите:

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

Теперь второе отражение находится вокруг главной диагонали, подобно транспонированию матрицы, меняя элементы по диагонали симметричным образом:

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

Оба отражения могут быть сделаны итеративно, поменяв отдельные элементы, поэтому они могут быть выполнены на месте.Это не имеет значения, если матрица 1D или 2D.

C ++ пример вращения на месте (представление матрицы в 1D-матрице):

const int ROWS = 4;
const int COLS = ROWS;
int A[ROWS*COLS];

int index(int row, int col) { return col + COLS * row; }
void swap(int i, int j) { int a = A[i]; A[i] = A[j]; A[j] = a; }

// x-axis reflection
for(int row_i = 0 ; row_i < ROWS / 2; ++row_i) {
    int row_j = ROWS - row_i - 1;
    for(int col_i = 0 ; col_i < COLS ; ++col_i)
        swap( index(row_i, col_i), index(row_j, col_i) );
}

// diagonal reflection
for(int row_i = 0 ; row_i < ROWS; ++row_i) {
    for(int col_i = row_i + 1 ; col_i < COLS ; ++col_i)
        swap( index(row_i, col_i), index(col_i, row_i) );
}