矩阵圆移 [英] 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.

例如

1 2 3
4 5 6
7 8 9

右移

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.

降档

9 7 8
3 1 2
6 4 5

推荐答案

也许像这样，

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> >内部. ;-) 是的，它确实支持随机访问.双端队列不是列表.另外，您无需再为模运算烦恼.

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.

这篇关于矩阵圆移的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！