从在相同索引处的值差异最小的列表中查找对

Question

给出表单列表的列表：

list = [index, number1, number2]
list_of_lists = [list1, list2, list3, ...]

您如何找到差异最大的列表对，例如数字1以最pythonic的方式？

示例：

list_of_lists = [[0, 13, 48], [1, 28, 9199], [2, 11, 128], [3, 9, 40]]
pairs = [[[1, 13, 48],[2, 11, 128]], [[2, 11, 128], [3, 9, 40]]]

因为abs(13-11) = abs(11-9) < abs(13-9) < abs(13-28) < abs(28-11) < abs(28-9)。到目前为止，我使用的方法是使用循环遍历所有列表，检查差异值并将其与到目前为止的差异值进行比较，希望仅检查一次。

lst = [list1, list2, list3, ...]
diff = 10000000000
candidates = []
for idx, c in enumerate(lst):
    for i in range(idx+1, len(lst)):
        current_diff = abs(c[0] - lst[i][0])
        if current_diff < diff:
            diff = current_diff
            candidates = []
            candidates.append([c, lst[i]])
        elif current_diff == diff:
            candidates.append([c, lst[i]])

出于多种原因，这似乎不太雅致。特别是“ diff”初始值的任意选择。

是否有一种通用且更好的方法，如上面的示例所示，取决于对特定值的某种比较，从列表列表中选择列表/列表对？

Answer 1

如果我们将您的数据视为矩阵中的行的列表，那么您正在寻找同一column中的一对数字，这些数字对应尽可能靠近。查找列中最接近的两个元素的有效方法是对列进行排序，然后遍历其相邻对。]

• 首先，我们必须构建要搜索的列。
• 然后我们必须对列进行排序。 （当然）这会改变顺序，因此我们将每个元素与其所在行的索引配对，以便以后可以恢复行。
• 我们可以使用zip在已排序的列中找到相邻的对，其中迭代器是“向前”的一步。
• 保持最接近的对的逻辑就像您的原始代码，但是初始化diff = math.inf而不是大的有限数，并通过将elif更改为if来保存一些重复的代码。

实施：

import math

def closest_pairs(rows, column_index):
    column = sorted((a[column_index], i) for i, a in enumerate(rows))

    candidates = []
    diff = math.inf

    # iterator which is one step ahead
    ahead = iter(column)
    next(ahead)

    for (x, i), (y, j) in zip(column, ahead):
        current_diff = y - x
        if current_diff < diff:
            candidates.clear()
            diff = current_diff
        if current_diff == diff:
            i, j = sorted([i, j])
            candidates.append( (rows[i], rows[j]) )

    return candidates

示例：

>>> lst = [[0, 28, 9199], [1, 13, 48], [2, 11, 128]]
>>> closest_pairs(lst, 1)
[([1, 13, 48], [2, 11, 128])]
>>> closest_pairs(lst, 0)
[([0, 28, 9199], [1, 13, 48]), ([1, 13, 48], [2, 11, 128])]

第1列中最接近的对是13, 11；在第0列中，0, 1和1, 2都最接近相等。

对于具有n行的矩阵，与原始O（n²）蛮力解决方案相比，此解决方案的时间复杂度为O（n log n）。