Inplace Rotation Of A Matrix
Solution 1:
Always use numpy for matrix operations. I'll assume an m*n numpy array arr. I first did a transpose using the np.transpose function and then I flipped it using the np.fliplr function.
output = np.fliplr(np.transpose(arr))
As mentioned in the comments, there is no way to do an in-place replace without a temporary variable for rectangular matrices. It's better to simulate the behavior (if storage is your concern) using a function like this,
def clockwise(matrix, row, column):
return matrix[-(column+1)][row]
Solution 2:
The other answers have rightly suggested rot90 or transpose and fliplr. If you dig into their code, you see that the action can be reduced to a transpose and a reverse indexing:
In [467]: arr=np.arange(1,26).reshape(5,5)
In [468]: arr.transpose()
Out[468]:
array([[ 1, 6, 11, 16, 21],
[ 2, 7, 12, 17, 22],
[ 3, 8, 13, 18, 23],
[ 4, 9, 14, 19, 24],
[ 5, 10, 15, 20, 25]])
In [469]: arr.transpose()[:,::-1]
Out[469]:
array([[21, 16, 11, 6, 1],
[22, 17, 12, 7, 2],
[23, 18, 13, 8, 3],
[24, 19, 14, 9, 4],
[25, 20, 15, 10, 5]])
Individually transpose and [:,::-1] produce views. That is, the array is new, but it shares a data buffer with the original. But together, numpy has to make a copy. In other words, you can't get the numbers [21, 16, 11,...] from [1,2,3,...] without reordering them.
Both transpose and [::-1] indexing are implemented in compiled code. transpose is actually a 'superficial' action, changing array shape and strides (and order), but not rearranging any values. By itself, [:,::-1] be a strides change, but with the order change it also has to perform an array copy.
The gory details
In [470]: arr.__array_interface__
Out[470]:
{'data': (151576248, False),
'descr': [('', '<i4')],
'shape': (5, 5),
'strides': None,
'typestr': '<i4',
'version': 3}
In [471]: arr1 = arr.transpose()
In [472]: arr1.__array_interface__
Out[472]:
{'data': (151576248, False),
'descr': [('', '<i4')],
'shape': (5, 5),
'strides': (4, 20),
'typestr': '<i4',
'version': 3}
In [473]: arr2 = arr1.copy()
In [474]: arr2.__array_interface__
Out[474]:
{'data': (154237272, False),
'descr': [('', '<i4')],
'shape': (5, 5),
'strides': None,
'typestr': '<i4',
'version': 3}
In [475]: arr3 = arr2[:,::-1]
In [476]: arr3.__array_interface__
Out[476]:
{'data': (154237288, False),
'descr': [('', '<i4')],
'shape': (5, 5),
'strides': (20, -4), # or (4,-20) without the explicit copy()'typestr': '<i4',
'version': 3}
A list version
Here's a pure Python list implementation. zip(*) is a list version of transpose. And [::-1] reverses lists just as it does arrays.
In [479]: alist1=arr.tolist()
In [480]: alist1
Out[480]:
[[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25]]
In [481]: alist2=list(zip(*alist1))
In [482]: alist2
Out[482]:
[(1, 6, 11, 16, 21),
(2, 7, 12, 17, 22),
(3, 8, 13, 18, 23),
(4, 9, 14, 19, 24),
(5, 10, 15, 20, 25)]
In [483]: alist3=[l[::-1] for l in alist2]
In [484]: alist3
Out[484]:
[(21, 16, 11, 6, 1),
(22, 17, 12, 7, 2),
(23, 18, 13, 8, 3),
(24, 19, 14, 9, 4),
(25, 20, 15, 10, 5)]
or in one line:
[list(l[::-1]) for l in zip(*alist1)]
That inner list is needed to make a list of lists rather than list of tuples.
This list code works if the 'matrix' is not square. But it is making a number of copies of the lists along the way. But that is typical of Python's way with lists. It is nearly always easier to create a new list from the old (via list comprehensions) than to mutate the original. Your rotate function is proof of that. I can't tell at a glance what is doing. You have obscure ranges like n//2 and m-1-i. And you can't handle the case where n and m differ (so the resulting outer list has a different length than the original).
Keep in mind that lists contain pointers, not values. A 'matrix' list is just one list that contains pointers to other lists, which themselves point to values stored else where in memory.
=======================
Some timings
In [493]: %%timeit alist=arr.tolist()
...: rotate(alist)
10000 loops, best of 3: 21 µs per loop
In [494]: %%timeit alist=arr.tolist()
...: [list(row[::-1]) for row in zip(*alist)]
100000 loops, best of 3: 6.83 µs per loop
the pure array operation is much faster:
In [495]: timeit arr.transpose()[:,::-1]
The slowest run took 11.51 times longer....
1000000 loops, best of 3: 1.46 µs per loop
but turning a nested list into an array does take time
In [496]: %%timeit alist=arr.tolist()
...: np.array(alist).transpose()[:,::-1]
...:
100000 loops, best of 3: 11.7 µs per loop
For comparison, the direct numpy function - this array is small enough that a couple of layers of function calls chews up a significant amount of time.
In [523]: timeit np.rot90(arr,-1)
The slowest run took 5.06 times longer ...
100000 loops, best of 3: 6.18 µs per loop
I imagine that with bigger arrays, the in-placerotate will get relatively worse - until the others produce MemoryErrors.
Solution 3:
To rotate a 2-D matrix by 90 clockwise in-place(without allocated new matrix), it will include two steps as follows.
- Inverse rows in matrix
- Transpose the whole matrix
"""Example:
[ [ [
[1,2,3], [7,8,9] [7,4,1]
[4,5,6], -> [4,5,6] -> [8,5,2]
[7,8,9] [1,2,3] [9,6,3]
] ] ]
"""defrotate(matrix):
rows = len(matrix)
columns = len(matrix[0])
# inverse rowfor i inrange(rows//2):
matrix[i], matrix[columns-i-1] =\
matrix[columns-i-1], matrix[i]
# transposefor i inrange(rows):
for j inrange(i):
matrix[i][j], matrix[j][i] =\
matrix[j][i], matrix[i][j]
if __name__ == "__main__":
matrix = [[1,2,3],[4,5,6],[7,8,9]]
rotate(matrix)
print(matrix)
Solution 4:
martianwars' answer is great. There is a more direct route with NumPy, however:
np.rot90(arr)
The only fly in the ointment is that rot90 rotates the array counterclockwise whereas the OP's example seemed to want clockwise. No problem, though. There's a parameter k for how many rotates to (logically) perform. For i clockwise rotates:
np.rot90(arr, 4-i)
Post a Comment for "Inplace Rotation Of A Matrix"