矩阵循环移位

Question

有人知道一种有效的方法来进行矩阵的循环右移吗？顺便说一下，这个矩阵是二进制的，但是解决非二进制矩阵的方法也可以。

目前，我正在考虑为矩阵的行实现一个循环数组，并在需要进行移位操作时更新每一行。

另一种我正在考虑的方法是实现一个指向由向量表示的列（矩阵的列）的指针向量，并在发生移位操作时交换它们。

例如。

1 2 3
4 5 6
7 8 9

右移

3 1 2
6 4 5
9 7 8

另一个问题是如果我需要将矩阵向下移动，所有这些解决方案都会出现问题。要高效地实现这两个操作，完全超出了我的能力。

下移操作

9 7 8
3 1 2
6 4 5

- Jacob

---

定义位矩阵。该矩阵如何表示？例如，大小需要满足哪些要求？是固定的还是动态的？等等等等。将序列向左或向右旋转只是循环遍历序列并在某个临时变量中记忆一个值的简单问题。 - sellibitze

矩阵可以用任何形式表示。存储的数据将是布尔值。每个矩阵的大小可以从大约300x300到1000x1000不等（不一定是正方形）。是的，就是这样。但如果我们在左右旋转时交换列指针而不是实际复制值，那么它会更有效率。 - Jacob

deque只是类似于您想要的东西的示例。顺便说一下：它确实支持快速随机访问。 - sellibitze

我的错误，我在想队列。 - Jacob

请随意给您喜欢的答案点赞 :) - sellibitze

Answer 1

也许可以像这样，

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> >。;-) 是的，它确实支持随机访问。deque不是列表。此外，您不再需要担心模算术问题。

- sellibitze

---

vector<bool> 不是应该非常有问题吗？ - Jacob

在这种情况下，我认为使用std::vector<bool>没有问题。 - sellibitze

Answer 2

不确定您的意思。通常，右移操作应用于缓冲区或行向量。答案将取决于矩阵的存储方式。

如果内存布局允许，一种有效的旋转数组的方法是将第一个值复制到数组的末尾，然后将指针向上移动一个元素。这仅在为数组分配足够的空间并且不旋转太多次时才有效。

或者，您可以将数组保持在原地，并具有指向“左端”的额外指针，在其他操作中正确处理所有包装。

否则，您可能需要执行大量的memcopying。

编辑：我看到您刚刚更新了问题以包括此答案。

其他编辑：从示例中，您似乎不需要单独移动行和列。如果是这样，那么您只需要存储“左上”索引的坐标，并相应地修改所有矩阵操作以适当地查找数据结构中的值。

那么对您来说问题就变成了效率问题。您是否要执行许多移位操作？如果不是，那么通过额外的查找减慢所有乘法操作可能不值得。

如果你使用查找的方法，千万不要使用取模运算符。这样非常低效。相反，对于位移操作，只需要检查是否大于行或列的长度，并在需要时减去长度即可。

- user66363

Answer 3

另一种我正在考虑的方法是实现一个指向由向量表示的列（矩阵的）指针的向量，并在发生移位操作时交换它们。

我会为列（水平移位）做这个，还会有另一个向量用于行（垂直移位）。

我还会创建一个Matrix对象来封装您的“真实”矩阵和这两个向量。您对象的getter/setter将引用这两个向量以访问您“真实”矩阵中的数据，并且您将拥有像“horizontalShift(...)”和“verticalShift(...)”这样的方法，仅交换您两个向量中的值，就像您建议的那样。

这会是最快的实现吗？访问数据还需要进行一次间接寻址（尽管仍然是O(1)），并且使用向量进行垂直移位的水平移位将是O(m)，垂直移位将是O(n)（对于n乘m的矩阵）。

- Jodi

Answer 4

我通过逆时针移位实现了一个递归的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;
}

- Charlie

Answer 5

使用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的对应关系，有一个非常有用的参考指南。

- Girardi

Answer 6

有一些方法可以使移位本身非常快，但在尝试“使用”矩阵时会导致效率低下，例如打印、点积和叉积。

例如，如果我定义了一个像“int m[3][2];”这样的矩阵，我可能只使用索引来定义第一列索引。因此，移位只是对该索引进行加减（不修改数据）。

另一个例子；如果您想将矩阵限制为二进制，则可以将矩阵打包到单个变量中并使用位移（左旋转\右旋转）。

然而，这两种方法都会使其他操作更加复杂。

我想这完全取决于矩阵将如何使用以及您希望它有多通用。

- gatorfax

---

循环移位对于位矩阵来说会非常复杂，因为需要大量的记录，这可能会超过应用程序的实际需求。而且如果要在行和列两个方向上进行移位，情况会更加复杂。 - Jacob

Answer 7

我已经编写了代码，可以按层循环方式旋转数组。

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

示例代码可正常工作：

- Priyansh Choudhary