Matrix Circular Shift

Question

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

Answer 1

Not sure what you mean exactly. Usually right-shift is applied to a buffer or row vector. The answer will depend on how your matrix is stored.

An efficient way to rotate an 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 up one element. This will only work if you allocate enough room for the array and don't rotate too many times.

Or, you can just keep the array in place and have an extra pointer to the "left end", taking care to handle all the wrapping around correctly in your other operations.

Otherwise, you will probably have to perform a lot of memcopying.

Edit: I see you just updated the question to include this answer.

Other edit: From the examples, you don't seem to need to shift the rows and columns independently. If that is the case, then you just need to store the coordinates of the "top left" index and modify all the matrix operations to lookup values in the data structure appropriately.

The issue for you then becomes a question of where you want the efficiency. Are you going to be performing many shift operations? If not, then it might not be worth slowing down all the multiplication operations with an extra lookup.

And if you do use the lookup idea, definitely DO NOT use a mod operator. It is incredibly inefficient. Instead, for a shift, just test for greater than row or column length and subtract the length when needed.

Answer 2

There are methods that make doing the shift itself very fast, but result in inefficiencies when trying to 'use' the matrix, e.g. print, dot\cross products.

For example, if I had a matrix defined like "int m[3][2];" I might just use an index to define the first column index. Thus a shift is just an add\subtract of that one index (no modification of the data).

Another example; if you want to restrict the matrix to being binary, you could pack the matrix into a single variable and use bit shifts (rotate left\right).

Both of these methods would make other operations more complex however.

I guess it all depends on the scope of how the matrix is going to be used and how generic you want it to be.

Answer 3

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.

I would do this for the columns (horizontal shift) and another vector for the 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 would reference those two vectors to access data in your "real" matrix and you would have methods like "horizontalShift(...)" and "verticalShift(...)" that only swap values in your two vectors, like you suggested.

Would it be the fastest implementation ? There one more indirection to access the data (still O(1) though) and the swapping would be O(m) for horizontal shift and O(n) for vertical shift (for a n by m matrix) using vectors.

Answer 4

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.