时间戳

首页 > 解决方案 > 最大化二维数组的第n行总和所需的最小交换？

python - 最大化二维数组的第n行总和所需的最小交换？

问题描述

我正在尝试不同的数组大小和元素。为简单起见，我采用了一个大小为 3x3 的数组。以二维列表的形式如下：

input_matrix = [[80,81,84],[69,80,51],[13,37,65]]

那么，什么可能是最好的方法呢？如果我使用嵌套循环，那么对于我想要避免的具有 O(n^2) 复杂性的简单任务来说，这将是一种过度杀伤力。

编辑1：

通过求和最大化，我的意思是我可以交换数组中的元素，并且对于第一行中的每个排列，都会有不同的总和。那么我需要多少次交换才能获得这样的安排

标签： pythonarrays

解决方案

如果您只能跨列交换：

通过行最大化，我假设您的意思是您可以在数组中垂直交换以使行最大化。在这种情况下，它可以通过 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数组中查找最大元素，找到它们的索引，如果它们不在所需的行中，它将它们计为交换并返回交换总数。功劳归于这个答案。

推荐阅读