Find Argmin To the Left/Right Of Each Index In Array

user_2955541 0
Viewed 148

Let say I have an array:

x = np.array([7., 5., 4., 1., 9., 2., 3., 6.,])

For each index, I want to find the argmin to the right of that index and also the argmin to the left of that index. Endpoints will have an an argmin of -1 when there is no index value available, so, the outputs would be:

left_argmins = [-1, 0, 1, 2, 3, 3, 3, 3]
right_argmins = [3, 3, 3, 5, 5, 6, 7, -1]

A naive approach (but slow approach) would be:

right_argmins = np.full(len(x), -1)

for i in range(len(x)):
    min_val = np.inf
    idx = -1
    for j in range(i+1, len(x)):
        if x[j] < min_val:
            min_val = x[j]
            idx = j
    right_argmins[i] = idx

left_argmins = np.full(len(x), -1)

for i in range(len(x)):
    min_val = np.inf
    idx = -1
    for j in range(i):
        if x[j] < min_val:
            min_val = x[j]
            idx = j
    left_argmins[i] = idx

What's the best way to accomplish this in NumPy?

Additionally, what would I do if I needed to do this for a 2D array?

numpy python
3 Answers

Create a matrix that has a lower triangle of infinity, then use broadcasting to make it take up one element of your array at a time. After that a simple argmin will do the job:

lower_tri = np.ones((len(x), len(x)))
lower_tri[np.tril(lower_tri, -1)==1] = float('inf')
lower_tri = lower_tri * x
np.argmin(lower_tri, axis=1)

results in

array([3, 3, 3, 3, 5, 5, 6, 7])

For the other direction, just use the upper triangle instead:

upper_tri = np.ones((len(x), len(x)))
upper_tri[np.triu(upper_tri, 1)==1] = float('inf')
upper_tri = upper_tri * x
np.argmin(upper_tri, axis=1)
# array([0, 1, 2, 3, 3, 3, 3, 3])

then you can append or prepend -1 as desired.

but bear in mind that this uses O(n^2) memory which might be relevant is x is large.

user_10117240

You can accumulate the indexes that result in the unique array of argsort indices applying minimum operator:

argidx = np.argsort(x)
u, idx = np.unique(argidx, return_index=True)
left_argmins = argidx[np.minimum.accumulate(idx)]
right_argmins = argidx[np.minimum.accumulate(idx[::-1])][::-1]

Output:

left_argmins: [0, 1, 2, 3, 3, 3, 3, 3]
right_argmins: [3, 3, 3, 3, 5, 5, 6, 7]
user_30448250

You can use indexing to get arrays of only the values to the left and right of the index, then call the argmin method for those arrays.

x = np.array([7., 5., 4., 1., 9., 2., 3., 6.,])

left_argmins = []
right_argmins = []
for i in range(len(x)):
    to_left = x[:i]
    if to_left.any():
        left_argmins.append(to_left.argmin())
    else:
        left_argmins.append(-1)
    to_right = x[i + 1:]
    if to_right.any():
        right_argmins.append(to_right.argmin() + (i + 1))
    else:
        right_argmins.append(-1)
user_87164010
Related