Матричный круговой сдвиг

Что-то вроде этого, возможно,

class matrix {
    std::vector<bool> elements;
    int rows, cols, row_ofs, col_ofs;

    std::size_t index(int r, int c) {
        r = (r + row_ofs) % rows;
        c = (c + col_ofs) % cols;
        return std::size_t(r)*cols + c; // row major layout
    }
public:
    matrix() : rows(0), cols(0) {}
    matrix(int r, int c)
    : elements(std::size_t(r)*c), rows(r), cols(c) {}

    int num_rows() const { return rows; }
    int num_cols() const { return cols; }

    std::vector<bool>::reference operator()(int r, int c) {
        return elements.at(index(r,c));
    }

    bool operator()(int r, int c) const {
        return elements.at(index(r,c));
    }

    void rotate_left()  { col_ofs = (col_ofs+1     ) % cols; }
    void rotate_right() { col_ofs = (col_ofs+cols-1) % cols; }
    void rotate_up()    { row_ofs = (row_ofs+1     ) % rows; }
    void rotate_down()  { row_ofs = (row_ofs+rows-1) % rows; }
};

(непроверено)

Изменить: Вот альтернатива: используйте std :: deque ‹std :: deque ‹T›› внутри. ;-) Да, он действительно поддерживает произвольный доступ. Двухсторонняя очередь - это не список. Кроме того, вам больше не нужно возиться с арифметикой по модулю.

Не уверен, что вы имеете в виду. Обычно сдвиг вправо применяется к буферу или вектору-строке. Ответ будет зависеть от того, как хранится ваша матрица.

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

Или вы можете просто оставить массив на месте и иметь дополнительный указатель на «левый конец», позаботившись о том, чтобы правильно обрабатывать все обертывания в других ваших операциях.

В противном случае вам, вероятно, придется много копировать в память.

Изменить: я вижу, вы только что обновили вопрос, чтобы включить этот ответ.

Другое редактирование: Судя по примерам, вам не нужно отдельно сдвигать строки и столбцы. Если это так, то вам просто нужно сохранить координаты «верхнего левого» индекса и соответствующим образом изменить все операции с матрицами для поиска значений в структуре данных.

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

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

Другой метод, который я рассматривал, заключался в реализации вектора указателей на столбцы (матрицы), представленных векторами, и их перестановка местами при выполнении операции сдвига.

Я бы сделал это для столбцов (горизонтальный сдвиг) и другого вектора для строк (вертикальный сдвиг).

Я бы также создал объект Matrix, чтобы инкапсулировать вашу «настоящую» матрицу и эти два вектора. Геттеры / сеттеры вашего объекта будут ссылаться на эти два вектора для доступа к данным в вашей «реальной» матрице, и у вас будут такие методы, как «horizontalShift (...)» и «verticalShift (...)», которые меняют только значения в вашем два вектора, как вы и предложили.

Будет ли это самая быстрая реализация? Есть еще одно косвенное обращение к данным (хотя все еще O (1)), и замена будет O (m) для горизонтального сдвига и O (n) для вертикального сдвига (для матрицы n на m) с использованием векторов.

Существуют методы, которые делают сам сдвиг очень быстрым, но приводят к неэффективности при попытке `` использовать '' матрицу, например печать, точечные \ перекрестные произведения.

Например, если бы у меня была матрица, определенная как «int m [3] [2];» Я мог бы просто использовать индекс для определения индекса первого столбца. Таким образом, сдвиг - это просто добавление \ вычитание этого одного индекса (без изменения данных).

Другой пример; если вы хотите, чтобы матрица была двоичной, вы можете упаковать матрицу в одну переменную и использовать битовые сдвиги (повернуть влево \ вправо).

Однако оба эти метода усложнили бы другие операции.

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

С помощью библиотеки Eigen очень просто:

Eigen::Matrix<int, 3, 3> A;
A << 1, 2, 3,
    4, 5, 6,
    7, 8, 9;
std::cout << A << std::endl << std::endl;
// Right-shift:
A.col(0).swap(A.col(1));
A.col(0).swap(A.col(2));
std::cout << A << std::endl << std::endl;
// Down-shift:
A.row(0).swap(A.row(1));
A.row(0).swap(A.row(2));
std::cout << A << std::endl << std::endl;

Существует очень полезное справочное руководство для соответствия Eigen-MATLAB.

Я реализовал рекурсивную версию C ++ с помощью сдвига против часовой стрелки:

// rotateMatrix.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;

void rotatematrix(int M[][3], int row, int col, int rowLen, int colLen)
{
    //rowLen & colLen are always the orginal matrix total length
    // playRows & playCols are the size for the current recuision
    // row & col are the starting position related to the original matrix(0,0)
    int playRows = rowLen - 2*row ;
    int playCols = colLen - 2*col;

    if (playCols <= 1 || playRows <= 1)
        return;

    //row,col is the starting point pointing to the top left corner element
    if (rowLen <= 1 || colLen <= 1) return;

    int tmp = M[row][col];

    //left shift the top row by one element
    for (int j = col; j <= playCols + col - 2; ++j)
        M[row][j] = M[row][j + 1];

    // up shift the right colunm by one position
    for (int i = row; i <= playRows + row - 2; ++i)
        M[i][col + playCols - 1] = M[i + 1][col + playCols - 1];

    //right shift the bottom row by one
    for (int j = col + playCols - 2; j >= col; --j)
        M[row+playRows-1][j+1] = M[row+playRows-1][j];

    // down shift the left col by one
    for (int i = row + playRows - 2; i >= row; --i)
        M[i+1][col] = M[i][col];

    M[row + 1][col] = tmp;


    rotatematrix(M, ++row, ++col, rowLen, colLen);
}

int _tmain(int argc, _TCHAR* argv[])
{
    // Test Case 1
    /*
    int a[4][4] = { { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 10, 11, 12 },
    { 13, 14, 15, 16 } };
    int R = 4, C = 4;*/

    // Tese Case 2
    int R = 3, C = 3;
    int a[3][3] = {{1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
    };

    for (int i = 0; i<R; i++)
    {
        for (int j = 0; j<C; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }

    rotatematrix(a, 0, 0, 3, 3);

    // Print rotated matrix
    for (int i = 0; i<R; i++)
    {
        for (int j = 0; j<C; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }

    return 0;
}

Я написал код для кругового вращения массива слой за слоем.

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int n;
    int value=1;
    scanf("%d",&n);
    int arr[n][n];
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    arr[i][j]=value++;
    

  
    for(int i=0;i<n;i++)
    {
    for(int j=0;j<n;j++)
    printf("%d\t",arr[i][j]);
    printf("\n");
    }
    
    for(int r1=0,r2=n-1,c1=0,c2=n-1;r1<=r2;r1++,r2--,c1++,c2--)
    {
    int temp=arr[c1][r2];
    
    for(int i=r2;i>r1;i--)
    arr[c1][i]=arr[c1][i-1];
    
    int temp2=arr[c2][r2];
    
    for(int i=c2;i>c1;i--)
    if(i!=c1+1)
    arr[i][r2]=arr[i-1][r2];
    else
    arr[i][r2]=temp;

    temp=arr[c2][r1];
    
    for(int i=r1;i<r2;i++)
    if(i!=r2-1)
    arr[c2][i]=arr[c2][i+1];
    else
    arr[c2][i]=temp2;
    
    for(int i=c1;i<c2;i++)
    if(i!=c2-1)
    arr[i][r1]=arr[i+1][r1];
    else
    arr[i][r1]=temp;
    
    
    }
    printf("\n\n");
    for(int i=0;i<n;i++)
    {
    for(int j=0;j<n;j++)
    printf("%d\t",arr[i][j]);
    printf("\n");
    }
    return 0;
}

Пример рабочего кода: