Numpy: Найти уникальные максимумы вдоль обеих осей 2d матрицы

Question

Учитывая n на n квадратную матрицу M, как эффективно найти все (i,j), 0 <= i,j < n там, где нет k, 0 <= k < n таких, что:

1. M[i,j] < M[k,j]
2. M[i,j] < M[i,k]
3. M[i,j] < M[j,k]
4. M[i,j] < M[k,i]

Можно предположить, что матрица является верхнейдиагональ с M[i,i] == 0 для всех i.

Я бы хотел лучший алгоритм для этого и самую быструю реализацию с numpy / Python.

Я пробовал следующее:

maxcol = np.argmax(scores,axis=1)
maxrow = np.argmax(scores,axis=0)

pairs = []
seen  = set([])

for i1 in xrange(M.shape[0]):
    j1 = maxcol[i]
    if (not i1 in seen) and maxrow[j1] == i1:
        seen.add(j1)
        i2 = j1
        j2 = maxcol[i2]
        if (not j1 in seen) and maxrow[j2] == i2 and M[i2,j2] > M[i1,j1]:
            pairs.append([i2,j2])
            seen.add(j2)
        else:
            pairs.append([i1,j1])

Но это выглядит довольно грязно, поэтому я не доверяю этому.Я также надеялся на более элегантное решение.

Answer 1

Рассмотрим в качестве примера следующую матрицу:

import numpy as np

M = np.array([[0,8,2,3,4,5],[0,0,3,9,1,7],[0,0,0,5,4,7],[0,0,0,0,1,4],[0,0,0,0,0,3],[0,0,0,0,0,0]])
print(M)

[[0 8 2 3 4 5]
[0 0 3 9 1 7]
[0 0 0 5 4 7]
[0 0 0 0 1 4]
[0 0 0 0 0 3]
[0 0 0 0 0 0]]

Ожидаемый результат будет примерно таким:

[[0, 1],
 [1, 3],
 [2, 5]]

, которые являются координатами значений, которые являются самыми большими вдоль соответствующего столбца и строки.

Это верхняя диагональная матрица с диагональю 0. Идея состоит в том, чтобы вычислить максимум матрицы, используя np.amax ( подробнее здесь ) вдоль каждой оси и сравнить транспонированную матрицу с результатом. np.amax с axis=0 даст вам максимумы для каждого столбца, а np.amax с axis=1 даст вам максимумы для каждого ряда.

Решение может быть:

c = np.amax(M,axis=0) #maximas along column axis
l = np.amax(M,axis=1) #maximas along row axis

#comparison with transposed matrix
maskC = np.asarray(M.transpose()>=c) #mask of valid values for column maximas 
maskL = np.asarray(M.transpose()>=l) #mask of valid values for row maximas
mask=np.logical_and(maskC,maskL) # final mask

j,i = mask.nonzero() #keep only the coordinates where the mask is True

coordinates = np.stack([i,j],axis=1) #build an array with the resulting coordinates

Это дает:

array([[0, 1],
   [1, 3],
   [2, 5]])