最大化 2D 数组第 n 行之和所需的最小交换次数？

Question

我正在尝试不同的数组大小和元素。为了简单起见，我采用了一个大小为 3x3 的数组。二维列表的形式如下：input_matrix = [[80,81,84],[69,80,51],[13,37,65]]那么，最好的方法是什么？如果我使用嵌套循环，那么对于这种具有 O(n^2) 复杂度的简单任务来说，这将是一种过度杀戮，我想避免这种情况。编辑1：通过求和最大化，我的意思是我可以交换数组中的元素，并且对于第一行中的每个排列，都会有不同的总和。那么，我需要多少次交换才能获得这样的排列，即行的总和是通过将整个数组中的元素放入第一行可以实现的所有可能总和的最大值

Answer 1

如果只能跨列交换：

通过行最大化，我假设您的意思是您可以在数组中垂直交换以使行最大化。在这种情况下，可以通过 numpy 完成，如下所示：

(np.argmax(np.array(input_matrix), axis = 0)!=r).sum()

这里的技巧是找到每列的最大元素，然后如果它不在所需的行（即 r）中，则将其计为交换，因为这就是您需要交换和求和的地方。

如果您可以交换数组中的任何元素：

如果您可以从整个数组中获取值，则需要更复杂的机制，如下所示：

def largest_indices(ary, n):

    """Returns the n largest indices from a numpy array."""

    flat = ary.flatten()

    indices = np.argpartition(flat, -n)[-n:]

    indices = indices[np.argsort(-flat[indices])]

    return np.unravel_index(indices, ary.shape)

(largest_indices(np.array(input_matrix), len(input_matrix[0]))[0]!=r).sum()

它继续查找n数组中的最大元素，找到它们的索引，如果它们不在所需的行中，则将它们计为交换并返回交换总数。