查找具有唯一列的数组中每一行的最小值

Question

我需要找到数组中的行最小值，其中每个最小值都必须来自唯一的列。

np.min(arr, axis=1) 提供按行最小值，但可能包含多次相同的列。

例如，给定：

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

np.min(a, axis=1) 会输出：[4, 1, 7]

所有返回的最小值都来自第一列，但由于每列只能使用一次的限制，所需的输出将是 [5, 1, 9] 作为最佳分配：

1 是本例中的最小值，因此分配给第一列。 5 是可以分配给第二列的最佳最小值（因为第二行已被使用）。

我现在唯一的想法是使用某种递归来实现它（这很可能非常耗时，对吧？）。

Answer 1

您要查找的似乎是 N 个最小值，其中每个值的行和列索引都是唯一的（假设是 NxN 矩阵）。如果我们用它的初始坐标标记矩阵中的每个值，我们就可以 rear运行ge 它们而不会失去分辨它们来自哪里的能力。我不确定 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 秒内完成。您可以就地进行排序以提高 space 效率。

如果输入中有重复值，我也看不出为什么这不起作用。

Answer 2

使用 numpy 执行上述操作的更简单方法（可能不会更快），如果您知道数组值的上限：

# matrix is a numpy 2-D array, k is some arbirtary large value
mapping = [None]*matrix.shape[0] # row-column mapping for minimum value
tmp = matrix.copy()
for i in range(matrix.shape[0]):
        u, v = divmod(tmp.argmin(), tmp.shape[1])
        mapping[u]=v
        tmp[u,:]=k
        tmp[:,v]=k

查找具有唯一列的数组中每一行的最小值

Find minimum for every row in array with unique columns

python

arrays

numpy

constraints

minimum