고유 열이 있는 배열의 모든 행에 대한 최소값 찾기

찾고 있는 것은 각 값에 대한 행 및 열 인덱스가 고유한 N개의 최소값인 것으로 보입니다(NxN 행렬 가정). 초기 좌표로 행렬의 각 값에 태그를 지정하면 어디서 왔는지 알 수 있는 능력을 잃지 않고 재정렬할 수 있습니다. 에서 사용자 정의 키로 정렬하는 매끄러운 방법이 있는지 확실 numpy하지 않으므로 재귀 또는 역추적이 필요하지 않은 바닐라 Python 솔루션이 있습니다.

def idx_matrix(matrix):
    # return 1-D array of matrix values in (row_idx, col_idx, val) format
    return [(r, c, val) for r, row in enumerate(matrix)
                        for c, val in enumerate(row)]

def find_minima(indexed_vals, limit=0):
    # return array of indexed matrix values whose row and col indexes are unique
    minima = []
    rows = set()
    cols = set()
    for row, col, val in indexed_vals:
        if row not in rows and col not in cols:
            minima.append((row, col, val))
            if limit and len(minima) == limit:
                # optional optimization if you want to break off early
                # after you've found a value for every row
                break
            rows.add(row)
            cols.add(col)
    return minima

def sort_by_val(indexed_vals):
    # return indexed_vals sorted by original matrix value
    return sorted(indexed_vals, key=lambda x: x[2])

def sort_by_row(indexed_vals):
    # return indexed_vals sorted by row index
    return sorted(indexed_vals, key=lambda x: x[0])

def strip_indices(indexed_vals):
    # return a 1-D array with row and col index removed
    return [v[2] for v in indexed_vals]

def find_minima_by_row(matrix):
    # put it all together
    indexed = idx_matrix(matrix)
    indexed = sort_by_val(indexed)
    minima = find_minima(indexed)
    minima = sort_by_row(minima)
    return strip_indices(minima)

matrix = [[4, 5, 6],
          [1, 2, 3],
          [7, 8, 9]]
results = find_minima_by_row(matrix)
print(f'{results=}')

matrix = [[20, 17,  5, 13, 19],
          [11, 22,  8,  4,  9],
          [ 0, 10,  2, 16, 23],
          [ 1, 24, 21, 15, 14],
          [ 3, 12,  6,  7, 18]]
results = find_minima_by_row(matrix)
print(f'{results=}')

results=[5, 1, 9]
results=[5, 4, 0, 14, 12]

이것은 내 워크스테이션에서 2000x2000 매트릭스로 ~4초 안에 실행되었습니다. 공간을 좀 더 효율적으로 만들기 위해 제자리에서 정렬을 수행할 수 있습니다.

또한 입력에 반복되는 값이 있으면 이것이 작동하지 않을 이유가 없습니다.