Matrix Circular Shift
Asked Answered
A

7

3

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
Alloplasm answered 25/9, 2009 at 17:56 Comment(7)
define bit matrix. How is the matrix represented? What are the requirements in size for example? Fixed? Dynamic? etc etc etc. Rotating a sequence on to the left or right is simply a matter of looping over the sequence and memorizing one value in some temporary variable.Daglock
The matrix can be represented in any form. The data stored will be boolean values. The size of each matrix can range from around 300x300 to 1000x1000 (not necessarily square). And yes, it is just that. But it's more efficient if we swap pointers to columns around instead of actually copying values if we rotate it to the left or right.Alloplasm
Instead of actually moving/copying data you could simply write a class for storing matrices which supports fast rotation. See std::deque for example: tmp = deque.front(); deque.pop_front(); deque.push_back(tmp); All done in O(1)Daglock
Thanks, sorry for not mentioning, but I need random access to the matrices later and deque does not support that. And yes, maybe I could copy it to a vector array later.Alloplasm
deque was just an example of something that is similar to what you want. By the way: it does support fast random access.Daglock
My bad, I was thinking of queuesAlloplasm
Feel free to upvode any answer you like :)Daglock
D
2

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.

Daglock answered 25/9, 2009 at 19:17 Comment(2)
Isn't vector<bool> supposed to be really problematic?Alloplasm
In this case I don't see a problem with using std::vector<bool>Daglock
A
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.

Attraction answered 25/9, 2009 at 18:4 Comment(0)
R
1

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.

Radish answered 25/9, 2009 at 19:13 Comment(0)
U
0

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.

Unionize answered 25/9, 2009 at 18:40 Comment(1)
Wouldn't circular shifts be very complicated on a bit matrix such that the amount of bookkeeping might outweigh the application? And what about shifts in both directions (rows and columns)?Alloplasm
M
0

Using Eigen library it is very simple:

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;

There is a very useful reference guide for Eigen-MATLAB correspondence.

Mariejeanne answered 10/8, 2016 at 21:16 Comment(0)
M
0

I implemented a recursion C++ version by anti clock wise shift:

// 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;
}
Meza answered 10/4, 2018 at 7:21 Comment(0)
B
0

I have made code for rotating an array in circular fashion layer by layer.

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

Sample code working:

enter image description here

Bedbug answered 6/11, 2020 at 7:48 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.