Efficient way to shift 2D-matrices in both directions?

Question

Given a two dimensional matrix, e.g.

l = [[1,1,1],
     [2,5,2],
     [3,3,3]])

What is the most efficient way of implementing a shift operation on columns and rows?

E.g.

shift('up', l) 

[[2, 5, 2],
 [3, 3, 3],
 [1, 1, 1]]

but

shift('left', l) 

[[1, 1, 1],
 [5, 2, 2],
 [3, 3, 3]]

I'm using collections.deque on both depths because of this answer but while a 'up' or 'down' only requires 1 shift, a 'left' or 'right' requires N shifts (my implementation is using a for cycle for each row).

In C I think this can be improved using pointer arithmetic (see e.g. this answer).

Is there a better pythonic way?

EDIT:

By efficient I mean if there is a way of avoiding the N shifts.
We can assume the matrix is squared.
The shift can be in place.

Thanks to martineau for pointing out these important points of the question. I'm sorry I didn't pointed them out before.

Will the shift amount ever be more than the respective matrix dimension and if so what should happen? — martineau, Nov 09 '13 at 18:17
@martineau Efficient in the sense described in the question: it currently requires N shifts, and 1 shift would be the ideal; the shift amount I'm considering is 1, but feel free to generalize; Shift is the identity transformation when is of the size of the matrix. — Jorge Leitao, Nov 09 '13 at 20:37
If you had described the type of efficiency in your question, I wouldn't have need to ask for clarification. Here's a few more: Can the matrix be assumed to be square? Does the function shift the matrix in-place or return a new one? — martineau, Nov 10 '13 at 18:51
@martineau, you are right, I'm sorry. I edited the question to make it more clear. — Jorge Leitao, Nov 10 '13 at 19:54

Nima Mousavi · Accepted Answer · 2014-09-02T17:01:45.740

34

Numpy provides a method called roll() to shift entries.

>>> import numpy as np
>>> x = np.arange(9)
>>> x = x.reshape(3, 3)
>>> print(x)

[[0 1 2]
 [3 4 5]
 [6 7 8]]

>>> x = np.roll(x, -1, axis=0) # up
>>> print(x)

[[3 4 5]
 [6 7 8]
 [0 1 2]]

>>> x = np.roll(x, 1, axis=0) # down
>>> print(x)

[[0 1 2]
 [3 4 5]
 [6 7 8]]

>>> x = np.roll(x, 2, axis=1) # right
>>> print(x)

[[1 2 0]
 [4 5 3]
 [7 8 6]]

>>> x = np.roll(x, -2, axis=1) # left
>>> print(x)    

[[0 1 2]
 [3 4 5]
 [6 7 8]]

I guess that Numpy will be pretty efficient compared to most solutions
in terms of matrix operations and you won't be bound to a 2 dimensional matrix.

edited Sep 02 '14 at 17:01

answered Sep 02 '14 at 16:34

Nima Mousavi

1,601
2
21
30

I am marking this as the accepted answer because, even if not profiled to be faster, it is certainly more maintainable and Pythonic. – Jorge Leitao Dec 23 '17 at 17:38
@J.C.Leitão: I don't consider using a third-party library extension to do something more efficiently than Python very _pythonic_...also what exactly do you mean by "not profiled to be faster"? – martineau Dec 24 '17 at 00:08
The question does seem to suggest that a self implemented solution is wanted, although the headline does not. Anyways, how is using a third party library not pythonic? – Nima Mousavi Jan 08 '18 at 10:27

martineau · Answer 2 · 2018-02-04T18:04:11.437

Here's one fairly efficient way to do it that will work with non-square matrices:

DIRS = NONE, UP, DOWN, LEFT, RIGHT = 'unshifted', 'up', 'down', 'left', 'right'

def shift(matrix, direction, dist):
    """ Shift a 2D matrix in-place the given distance of rows or columns in the
        specified (NONE, UP, DOWN, LEFT, RIGHT) direction and return it.
    """
    if dist and direction in (UP, DOWN, LEFT, RIGHT):
        n = 0
        if direction in (UP, DOWN):
            n = (dist % len(matrix) if direction == UP else -(dist % len(matrix)))
        elif direction in (LEFT, RIGHT):
            n = (dist % len(matrix[0]) if direction == LEFT else -(dist % len(matrix[0])))
            matrix[:] = list(zip(*matrix))  # Transpose rows and columns for shifting.

        h = matrix[:n]
        del matrix[:n]
        matrix.extend(h)

        if direction in (LEFT, RIGHT):
            matrix[:] = map(list, zip(*matrix))  # Undo previous transposition.

    return matrix


if __name__ == '__main__':

    # Some non-square test matrices.
    matrix1 = [[1, 2, 3],
               [4, 5, 6],
               [7, 8, 9],
               [10, 11, 12]]

    matrix2 = [[1, 2, 3, 4],
               [5, 6, 7, 8],
               [9, 10, 11, 12]]

    def shift_and_print(matrix, direction, dist):
        GAP =  2  # Plus one for a ":" character.
        indent = max(map(len, DIRS)) + GAP
        print(direction
                + ': ' + (indent-2-len(direction))*' '
                + ('\n'+indent*' ').join(map(str, shift(matrix, direction, dist)))
                + '\n')

    for matrix in matrix1, matrix2:
        for direction in DIRS:
            shift_and_print(matrix, direction, 1)  # Printed results are cumulative.

Output (note that the results are cumulative since the operations are performed in-place and the shifting is applied to the result of the previous call):

no shift: [1, 2, 3]
          [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]

up:       [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]
          [1, 2, 3]

down:     [1, 2, 3]
          [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]

left:     [2, 3, 1]
          [5, 6, 4]
          [8, 9, 7]
          [11, 12, 10]

right:    [1, 2, 3]
          [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]

no shift: [1, 2, 3, 4]
          [5, 6, 7, 8]
          [9, 10, 11, 12]

up:       [5, 6, 7, 8]
          [9, 10, 11, 12]
          [1, 2, 3, 4]

down:     [1, 2, 3, 4]
          [5, 6, 7, 8]
          [9, 10, 11, 12]

left:     [2, 3, 4, 1]
          [6, 7, 8, 5]
          [10, 11, 12, 9]

right:    [1, 2, 3, 4]
          [5, 6, 7, 8]
          [9, 10, 11, 12]

Akavall · Answer 3 · 2013-11-09T17:09:57.257

Maybe something like this using numpy:

def shift(x, direction='up'):
    if direction == 'up':
        temp = range(x.shape[0])
        indicies = temp[1:] + [temp[0]]
        return x[indicies]
    elif direction == 'left':
        temp = range(x.shape[1])
        indicies = temp[1:] + [temp[0]]
        return x[:, indicies]
    else:
        print 'Error direction not known'

Result:

>>> shift(l, direction='up')
array([[2, 5, 2],
       [3, 3, 3],
       [1, 1, 1]])
>>> shift(l, direction='left')
array([[1, 1, 1],
       [5, 2, 2],
       [3, 3, 3]])
>>> shift(l, direction='to the moon')
Error direction not known

score 0 · Answer 4 · answered Nov 09 '13 at 18:03

This is a generic version you can rotate it in all four directions, any number of times

l = [[1,1,1],
     [2,5,2],
     [3,3,3]]

def shift(direction, count, myList):
    myLen = len(myList)
    if direction == "up":
        return [myList[i % myLen] for i in range(count, count + myLen)]
    elif direction == "down":
        return [myList[-i] for i in range(count, count - myLen, -1)]
    elif direction == "left":
        tlist = zip(*myList)
        return map(list, zip(*[tlist[i % myLen] for i in range(count, count + myLen)]))
    elif direction == "right":
        tlist = zip(*myList)
        return map(list, zip(*[tlist[-i] for i in range(count, count - myLen, -1)]))

print shift("up", 1, l)
print shift("up", 2, l)
print shift("down", 2, l)
print shift("down", 1, l)
print shift("left", 1, l)
print shift("right", 1, l)

Output

[[2, 5, 2], [3, 3, 3], [1, 1, 1]]
[[3, 3, 3], [1, 1, 1], [2, 5, 2]]
[[2, 5, 2], [3, 3, 3], [1, 1, 1]]
[[3, 3, 3], [1, 1, 1], [2, 5, 2]]
[[1, 1, 1], [5, 2, 2], [3, 3, 3]]
[[1, 1, 1], [2, 2, 5], [3, 3, 3]]

Admittedly the question is vague on a number of important points, but your code only works for square matrices -- so it may not be "generic" enough. — martineau, Nov 10 '13 at 18:45

Efficient way to shift 2D-matrices in both directions?

4 Answers4

Linked