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

Question

给出以下形式的列表列表：

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

你如何以最pythonic的方式找到差异最小的列表对，例如number1？

示例：

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

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

• 首先，我们必须构建您想要搜索的列。
• ，然后我们必须对该列进行排序。这改变了顺序(当然)，所以我们将每个元素与它所在行的索引配对，这样以后就可以恢复这些行。
• 我们可以使用zip在排序的列中找到相邻的对，其中的迭代器是“领先”一步。
• 保留最接近对的逻辑与原始代码类似，但初始化diff = math.inf而不是大的有限数，并通过将elif更改为elif来节省一些重复的代码

实施：

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 )。