Numpyic way to sort an ndarray clockwise?

Question

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.

Clearly I'm missing something that everyone else is seeing, but I do not understand the procedure for converting the given inputs into the given outputs is supposed to work. E.g. how does the input ([2, 4, 6], [1, 5, 3], [7, 9, 8]) get turned into the output [[1, 2, 3], [8, 9, 4], [7, 6, 5]] if not by some kind of arbitrary permutation? Based on the diagram I would have expected [2, 4, 6, 3, 8, 9, 7, 1, 5]. Would you consider editing the question to be a bit more clear about it? — David Z
– David Z, Commented Jul 13, 2021 at 21:49
@DavidZ Clearly you are missing the word "sort". I am trying to sort the array clockwise, not getting the sequence clockwise. If you read the expected output from 1 to 9, you will understand. — Shaun Han
– Shaun Han, Commented Jul 14, 2021 at 5:57
No, you're wrong. I'm not missing the word "sort". What do you mean by "sort the array clockwise", if not traversing it along the spiral indicated in your diagram? — David Z
– David Z, Commented Jul 14, 2021 at 7:25
@DavidZ OP means "take all the values in the array, sort them, then lay them out in a spiral". — AKX
– AKX, Commented Jul 14, 2021 at 7:29
@AKX Ahh, now I get it, thanks. That's much more clear; the expression "sort an array clockwise" makes no sense to me. I hope the question can be edited to clear that up (or I could make an edit myself but I don't want to infringe on Shaun's authorial discretion). — David Z
– David Z, Commented Jul 14, 2021 at 7:32

Guy · Accepted Answer · 2021-07-13 12:38:51Z

10

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]]

answered Jul 13, 2021 at 12:38

Guy

51.2k10 gold badges49 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

gvlasov · Accepted Answer · 2021-07-13 11:52:39Z

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

Collectives™ on Stack Overflow

Numpyic way to sort an ndarray clockwise?

What I have tried so far

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

What I have tried so far

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related