Matrix Circular Shift

Question

Does anyone know an efficient way of right circular matrix shift? Btw, the matrix is ​​binary, but the non-binary matrix solution method is also good.

Right now, I'm going to inject a circular array for the rows of my matrix and update each row whenever a shift operation is required.

Another method I considered was to implement a vector of pointers to columns (matrices) represented by vectors and swap them around when a shift operation occurs.

eg.

1 2 3 4 5 6 7 8 9 

right shift

 3 1 2 6 4 5 9 7 8 

Another problem arises with all these solutions, if I need to also shift the matrix. To perform both operations efficiently, this is completely outside of me.

Down shift

 9 7 8 3 1 2 6 4 5 

Answer 1

Something like this maybe

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

(unverified)

Edit: Here's an alternative: use std :: deque <std :: deque <T → internally. ;-) Yes, it supports random access. Deca is not a list. In addition, you no longer need to worry about modulo arithmetic.

Answer 2

Not sure what you mean. Typically, the right shift is applied to a buffer or line vector. The answer will depend on how your matrix is ​​stored.

An effective way to rotate the array, if the memory layout allows it, is to copy the first value to the end of the array, and then move the pointer to the array one element. This will only work if you allocate enough space for the array and will not alternate too many times.

Or you can just keep the array in place and add an extra pointer to the "left end", taking care to properly handle all wrappings in other operations.

Otherwise, you probably have to do a lot of memcopying.

Edit: I see that you just updated the question by including this answer.

Another edit: from the examples, you don't seem to need to change the rows and columns independently. If this is the case, then you just need to save the coordinates of the “upper left” index and accordingly change all operations with matrices to search values ​​in the data structure.

The problem for you then becomes the question of where you want efficiency. Will you perform many shift operations? If not, then perhaps you should not slow down all multiplication operations with an additional search.

And if you use the idea of ​​searching, definitely DO NOT use the mod statement. This is incredibly inefficient. Instead, to jump, just check the length of the row or column and subtract the length when necessary.

Answer 3

Another method I considered was to implement a vector of pointers to columns (matrices) represented by vectors and swap them around when a shift operation occurs.

I would do this for columns (horizontal shift) and another vector for rows (vertical shift).

I would also create a Matrix object to encapsulate your "real" matrix and these two vectors. The getters / setters of your object will reference these two vectors to access the data in your "real" matrix, and you will have methods such as "horizontalShift (...)" and "verticalShift (...)" that change only the values ​​in your two vectors, as you expected.

Will it be the fastest implementation? There is another indirect access to data (but still O (1)), and the replacement is O (m) for horizontal shift and O (n) for vertical shift (for matrix n by m) using vectors.

Answer 4

There are methods that make a very quick shift, but lead to inefficiency when trying to "use" the matrix, for example. print, dot \ cross products.

For example, if I had a matrix defined as "int m [3] [2];" I could just use an index to determine the first index of a column. Thus, a shift is simply adding / subtracting this one index (without changing the data).

Another example; if you want to limit the matrix to binary, you can pack the matrix into one variable and use bit shifts (rotate left / right).

Both of these methods will make other operations more complicated, however.

I assume that it all depends on how the matrix will be used, and how universal you want.

Answer 5

Using the Eigen library is very simple:

 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; 

There is a very useful reference guide for Eigen-MATLAB compliance.

Answer 6

I implemented a recursive version of C ++ using multi-frame shift:

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