Dynamic array rotation algorithm without additional memory?

Question

C++ / C#

Hello, what is the algorithm for rotating a matrix of different dimensions by 90 clockwise and counterclockwise. With additional memory, the task is trivial, but without it, it also has different dimensions ...
There is a dynamic array of dimensions mx n.
This code works for nxn dimensions:

int tmp;
 for(int i=0;i<n/2;i++)
 {
 for(int j=i;j<n-1-i;j++)
 {
 tmp = matr[i][j];
 matr[i][j] = matr[n-j-1][i];
 matr[n-j-1][i] = matr[n-i-1][n-j-1];
 matr[n-i-1][n-j-1] = matr[j][n-i-1];
 matr[j][n-i-1] = tmp;
 }
 }
}

How can you implement the rotation of a dynamic array (matrix), without additional memory?

Answer 1

Swap cells through sum and subtraction.

Answer 2

How can I implement the rotation of a dynamic array (matrix), without additional memory?

Something like this:

#include <stddef.h>
#include <stdio.h>

typedef int T;

void rotate(T *p, size_t m, size_t n, size_t (*turn)(size_t m, size_t n, size_t idx))
{
        size_t i, j, k;

        for (i = 0; i < m * n; ++i) {
                T tmp0, tmp1;

                for (j = 0; j < i; ++j) {
                        for (k = turn(m, n, j); k != i && k != j; k = turn(m, n, k)) {
                        }
                        if (k == i)
                                break;
                }
                if (j < i)
                        continue;

                tmp0 = p[i];
                for (j = turn(m, n, i); ; j = turn(m, n, j)) {
                        tmp1 = p[j];
                        p[j] = tmp0;
                        tmp0 = tmp1;
                        if (j == i)
                                break;
                }
        }
}

void dump(size_t m, size_t n, T p[m][n])
{
        size_t i, j;

        for (i = 0; i < m; ++i)
                for (j = 0; j < n; ++j)
                        printf("%d%s", p[i][j], j == n - 1 ? "\n" : ", ");
}

size_t turn_ccw(size_t m, size_t n, size_t idx)
{
        return (n - 1 - idx % n) * m + (idx / n);
}

size_t turn_cw(size_t m, size_t n, size_t idx)
{
        return (idx % n) * m + m - 1 - (idx / n);
}

#define M 5
#define N 7

int main()
{
        size_t i, j;
        T a[M][N];

        for (i = 0; i < M; ++i)
                for (j = 0; j < N; ++j)
                        a[i][j] = i * N + j;

        rotate(&a[0][0], M, N, turn_ccw);
        dump(N, M, (T (*)[M])&a[0][0]);
        printf("\n");
        rotate(&a[0][0], N, M, turn_cw);
        dump(M, N, (T (*)[N])&a[0][0]);
}

turnconverts the linear index of the element in the original array to the index of the element in the rotated array.
Looping over i permutes chains of elements mapped to each other starting at element i. The first loop over j checks to see if element i has already been swapped in an earlier chain. The second loop over j swaps one string.

Answer 3

First of all, consider the option of saving the "transposed matrix" flag and taking this flag into account in the algorithms. Moreover, it will speed up the work TWICE, because. traversing the column of the transposed matrix physically turns out to be a traversal along the row, which has a positive effect on the caching of the matrix data.

Answer 4

You can not rotate this rectangular "sausage" at all. And store the rotation vector. And overload the index operator so that access behaves according to the rules of affine transformations.