Jacob - 1 year ago 88
C++ Question

# Matrix Circular Shift

Does anyone know an efficient way to right circular-shift a matrix? Btw, the matrix is binary but a method to solve a non-binary matrix is also fine.

Right now, I'm thinking of implementing a circular array for the rows of my matrix and updating each row whenever a shift operation is required.

Another method, I was considering was implementing a vector of pointers to columns (of the matrix) represented by vectors and swapping them around when a shift operation occurs.

E.g.

``````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 shift the matrix down as well. To implement both operations efficiently, is completely beyond me.

Down-shift

``````9 7 8
3 1 2
6 4 5
``````

Something like this perhaps,

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

(untested)

Edit: Here's an alternative: Use std::deque<std::deque<T> > internally. ;-) Yes, it does support random access. A deque is not a list. Plus, you don't need to bother anymore with the modulo arithmetic.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download