0
212
ViewsNumpyic way to sort an ndarray clockwise?
I am trying to sort a numpy ndarray clockwise (in ascending order). You can understand it as taking all the values in the array, sort them, then lay them out in a clockwise spiral to a new array with the same shape. The directions of the clockwise spiral are shown below:
For example, say I have an array of
import numpy as np
a1 = np.array(([2, 4, 6],
[1, 5, 3],
[7, 9, 8]))
The expected output is
np.array([[1, 2, 3],
[8, 9, 4],
[7, 6, 5]])
If I have an array of
a2 = np.array(([2, 4, 6],
[1, 5, 3],
[7, 9, 8],
[12, 11, 10]))
The expected output is
np.array([[1, 2, 3],
[10, 11, 4],
[9, 12, 5],
[8, 7, 6]])
What I have tried so far
My idea is to track the row index x and the column index y of the moving iterator and the current index cur of the sorted flattened list sa. The number of rows to go through (lenr) and the number of columns to go through (lenc) are subtracted by 1 once the moving iterator passes lenr rows horizontally and lenc columns vertically. Here is the function that I managed to write:
def clockwise_sorted(a, key=None, reverse=False):
nr, nc = a.shape
res = a.tolist()
sa = a.ravel().tolist()
if key is None:
sa.sort(reverse=reverse)
else:
sa.sort(key=key, reverse=reverse)
res[0] = sa[:nc]
cur, lenr, lenc = nc, nr - 1, nc - 1
x, y = 0, nc - 1
while (lenc > 0 and lenr > 0):
# go down, then go left
for _ in range(lenr):
x += 1
res[x][y] = sa[cur]
cur += 1
for _ in range(lenc):
y -= 1
res[x][y] = sa[cur]
cur += 1
lenr -= 1
lenc -= 1
# go up, then go right
for _ in range(lenr):
x -= 1
res[x][y] = sa[cur]
cur += 1
for _ in range(lenc):
y += 1
res[x][y] = sa[cur]
cur += 1
lenr -= 1
lenc -= 1
return np.array(res)
For square matrices, my code works fine:
print(clockwise_sorted(a1))
#[[1 2 3]
# [8 9 4]
# [7 6 5]]
#%timeit 5.98 µs ± 413 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
But it doesn't work for non-square matrices:
print(clockwise_sorted(a2))
#[[ 1 2 3]
# [10 11 4]
# [ 9 9 5]
# [ 8 7 6]]
Clearly, it misses the 12 at [2,1].
Please note that I don't expect you to understand and fix my code. I don't like my code so much because I feel like there should be more numpyic ways to do this. Therefore, I want to see some numpyic solutions. However, it would be nice if someone can comment on what is wrong with my code.
2 answers
Answer question0
This is likely hardly the numpyiest solution, but I think it's a neat Pythonic solution, being a generator function that yields spiral coordinates in clockwise order that's then used to index the numpy array (which has to be transposed twice to get the coordinates right, but that's peanuts...).
import numpy as np
def spiral_coords(w, h):
maxx = w - 1
maxy = h - 1
minx = miny = 0
while (minx, miny) != (maxx, maxy):
for x in range(minx, maxx): # right
yield (x, miny)
yield (maxx, miny) # upper-right corner
for y in range(miny + 1, maxy): # down
yield (maxx, y)
yield (maxx, maxy) # lower-right corner
for x in range(maxx - 1, minx, -1): # left
yield (x, maxy)
yield (minx, maxy) # lower-left corner
for y in range(maxy - 1, miny, -1): # up
yield (minx, y)
minx += 1
miny += 1
maxx -= 1
maxy -= 1
yield (minx, miny) # final point
def clockwise_sorted(a):
a = a.T
nr, nc = a.shape
sa = a.ravel()
sa.sort()
res = np.zeros_like(a)
for (x, y), v in zip(spiral_coords(nr, nc), sa):
res[x, y] = v
return res.T
a2 = np.array(
[
[2, 4, 6],
[1, 5, 3],
[7, 9, 8],
[12, 11, 10],
]
)
print(a2)
print(clockwise_sorted(a2))
This outputs
[[ 2 4 6]
[ 1 5 3]
[ 7 9 8]
[12 11 10]]
[[ 1 2 3]
[10 11 4]
[ 9 12 5]
[ 8 7 6]]
If you don't necessarily need Numpy, you can also use the same generator to spiralize anything into e.g. a mapping of coordinates to letters:
coords = {(x, y): c for (x, y), c in zip(spiral_coords(6, 5), "Hello World! This is a spiral!")}
for y in range(5):
print("".join(coords.get((x, y), " ") for x in range(6)))
outputs
Hello
is aW
sal! o
iripsr
hT !dl
0
You can use numpy.rot90 with recursion to rotate clockwise over the array. Sort the values of the array after changing to 1d and edit the values in the array by it
def rotate(matrix, arr):
if not len(matrix):
return
matrix[0] = arr[:len(matrix[0])]
rotate(np.rot90(matrix[1:]), arr[len(matrix[0]):])
a1 = np.array(([2, 4, 6],
[1, 5, 3],
[7, 9, 8]))
sorted_arr = sorted(a1.ravel())
rotate(a1, sorted_arr)
print(a1)
Output
[[1 2 3]
[8 9 4]
[7 6 5]]