Efficient way to shift 2D matrices in both directions?

Question

Given a two-dimensional matrix, for example

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

What is the most efficient way to implement column and row shift operations?

eg.

 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 use collections.deque at both depths because of this answer , but while "up" or "down" only needs 1 shift, or "right" requires N shifts (my implementation uses a for loop for each line).

In C, I think this can be improved using pointer arithmetic (see, for example, this answer ).

Is there a better pythonic way?

EDIT:

• Effective I mean, if there is a way to avoid N shifts.
• We can assume that the matrix is ​​square.
• The offset may be in place.

Thanks to Martino for pointing out these important questions. I wish I had indicated them before.

Answer 1

The Numpy function provides a roll () method for switching records.

 >>> 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 think Numpy will be quite efficient compared to most solutions.
in terms of matrix operations, and you will not be attached to a two-dimensional matrix.

Answer 2

Here is one pretty effective way to do this that will work with non-quadratic 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. 

The conclusion ( note ) that the results are cumulative, since the operations are performed in place, and the shift 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] 

Answer 3

Maybe something like this with 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 

Answer 4

This is a generic version that you can rotate 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]]