目前,我正在考虑为矩阵的行实现一个循环数组,并在需要进行移位操作时更新每一行。
另一种我正在考虑的方法是实现一个指向由向量表示的列(矩阵的列)的指针向量,并在发生移位操作时交换它们。
例如。
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
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
也许可以像这样,
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不是列表。此外,您不再需要担心模算术问题。
不确定您的意思。通常,右移操作应用于缓冲区或行向量。答案将取决于矩阵的存储方式。
如果内存布局允许,一种有效的旋转数组的方法是将第一个值复制到数组的末尾,然后将指针向上移动一个元素。这仅在为数组分配足够的空间并且不旋转太多次时才有效。
或者,您可以将数组保持在原地,并具有指向“左端”的额外指针,在其他操作中正确处理所有包装。
否则,您可能需要执行大量的memcopying。
编辑:我看到您刚刚更新了问题以包括此答案。
其他编辑:从示例中,您似乎不需要单独移动行和列。如果是这样,那么您只需要存储“左上”索引的坐标,并相应地修改所有矩阵操作以适当地查找数据结构中的值。
那么对您来说问题就变成了效率问题。您是否要执行许多移位操作?如果不是,那么通过额外的查找减慢所有乘法操作可能不值得。
如果你使用查找的方法,千万不要使用取模运算符。这样非常低效。相反,对于位移操作,只需要检查是否大于行或列的长度,并在需要时减去长度即可。我通过逆时针移位实现了一个递归的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;
}
使用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的对应关系,有一个非常有用的参考指南。
有一些方法可以使移位本身非常快,但在尝试“使用”矩阵时会导致效率低下,例如打印、点积和叉积。
例如,如果我定义了一个像“int m[3][2];”这样的矩阵,我可能只使用索引来定义第一列索引。因此,移位只是对该索引进行加减(不修改数据)。
另一个例子;如果您想将矩阵限制为二进制,则可以将矩阵打包到单个变量中并使用位移(左旋转\右旋转)。
然而,这两种方法都会使其他操作更加复杂。
我想这完全取决于矩阵将如何使用以及您希望它有多通用。
我已经编写了代码,可以按层循环方式旋转数组。
#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;
}
示例代码可正常工作: