在Python中查找多个列表中最相似的数字

Question

在Python中，我有3个浮点数列表（角度），范围为0-360，并且这些列表的长度不同。我需要找到三元组（每个列表中取一个数字），使得它们之间的距离最小。（由于这是实际数据，很不可能存在任何相同的数字）。我考虑使用一种简单的最小标准差方法来衡量协议，但我不确定如何有效地实现它。我可以通过嵌套for循环遍历每个列表，比较每个可能组合的标准差，并且使用一个临时变量保存最佳匹配的三元组的索引位置，但我想知道是否有更好、更优雅的方法来完成类似的操作。谢谢！

- new_sysadmin

---

也许先对这三个列表进行排序，可以更容易地找到三元组。 - voithos

抱歉，我应该提到它们已经按升序排序了。 - new_sysadmin

有趣的问题。我认为你可以通过创建一个离散密度图并从最密集到最稀疏的地方进行检查来减少很多处理量，直到获得有效的解决方案。第一个有效的解决方案可能是最好的，因为所有后续的解决方案都出现在密度较低的区域，并且不太可能具有更大的差异。当我今天下班回家后，我会尝试一下并看看是否能够编写一个概念验证。 - Nisan.H

你是如何定义0/360边界的？它是循环的吗？ - Nisan.H

Nisan: 360被包装回0。在相位测量中存在固有的歧义（即角度是什么），但我已经在代码的其他地方处理过了，所以这不适用于这个问题。 - new_sysadmin

Answer 1

如果有针对此操作的已建立算法，我不会感到惊讶，如果有的话，您应该使用它。但是我不知道有没有这样的算法，所以我会稍微猜测一下。

如果我必须执行此操作，我会尝试的第一件事就是循环遍历所有可能的数字组合，并查看执行时间。如果您的数据集足够小，则不值得花费时间来发明一个聪明的算法。为了演示设置，我将包括示例代码:

# setup
def distance(nplet):
    '''Takes a pair or triplet (an "n-plet") as a list, and returns its distance.
    A smaller return value means better agreement.'''
    # your choice of implementation here. Example:
    return variance(nplet)

# algorithm
def brute_force(*lists):
    return min(itertools.product(*lists), key = distance)

对于大型数据集，我会尝试这样做：首先为第一个列表中的每个数字创建一个三元组，并将其第一个条目设置为该数字。然后遍历这个部分填充的三元组列表，并为每个三元组从第二个列表中选择最接近第一个列表中的数字，并将其设置为三元组的第二个成员。然后遍历三元组列表，并从前两个数字最接近的第三个列表中选择数字（根据你的协议度量衡）。最后，选择最佳结果。此示例代码演示了如何尝试在列表长度的运行时间保持线性。

def item_selection(listA, listB, listC):
    # make the list of partially-filled triplets
    triplets = [[a] for a in listA]
    iT = 0
    iB = 0
    while iT < len(triplets):
        # make iB the index of a value in listB closes to triplets[iT][0]
        while iB < len(listB) and listB[iB] < triplets[iT][0]:
            iB += 1
        if iB == 0:
            triplets[iT].append(listB[0])
        elif iB == len(listB)
            triplets[iT].append(listB[-1])
        else:
            # look at the values in listB just below and just above triplets[iT][0]
            # and add the closer one as the second member of the triplet
            dist_lower = distance([triplets[iT][0], listB[iB]])
            dist_upper = distance([triplets[iT][0], listB[iB + 1]])
            if dist_lower < dist_upper:
                triplets[iT].append(listB[iB])
            elif dist_lower > dist_upper:
                triplets[iT].append(listB[iB + 1])
            else:
                # if they are equidistant, add both
                triplets[iT].append(listB[iB])
                iT += 1
                triplets[iT:iT] = [triplets[iT-1][0], listB[iB + 1]]
        iT += 1
    # then another loop while iT < len(triplets) to add in the numbers from listC
    return min(triplets, key = distance)

事实上，我可以想象情况下这并不能找到最佳的三元组，例如如果第一个列表中的数字接近第二个列表中的数字，但与第三个列表中的任何数字都不接近。因此，您可以尝试对列表的所有6种可能的排序运行此算法。我无法想出一个具体的情况，其中它将无法找到最佳三元组，但可能仍然存在。在任何情况下，如果使用巧妙的实现，并假设列表已排序，则算法仍将是O（N）。

def symmetrized_item_selection(listA, listB, listC):
    best_results = []
    for ordering in itertools.permutations([listA, listB, listC]):
        best_results.extend(item_selection(*ordering))
    return min(best_results, key = distance)

另一个选择是计算列表1和列表2之间、列表1和列表3之间以及列表2和列表3之间的所有可能数字对。然后将这三个数字对列表一起排序，从最好到最差的一致性排序。从最接近的数字对开始，逐对浏览该列表，每当遇到与已经看过的数字对共享数字的数字对时，将它们合并成三元组。对于一种合适的一致性度量，一旦找到第一个三元组，那将给出您需要迭代的最大对距离，一旦达到它，您只需选择您找到的最接近的三元组即可。我认为这应该始终能够找到最佳的三元组，但由于需要对数字对列表进行排序，所以时间复杂度为O(N^2 log N)。

def pair_sorting(listA, listB, listC):
    # make all possible pairs of values from two lists
    # each pair has the structure ((number, origin_list),(number, origin_list))
    # so we know which lists the numbers came from
    all_pairs = []
    all_pairs += [((nA,0), (nB,1)) for (nA,nB) in itertools.product(listA,listB)]
    all_pairs += [((nA,0), (nC,2)) for (nA,nC) in itertools.product(listA,listC)]
    all_pairs += [((nB,1), (nC,2)) for (nB,nC) in itertools.product(listB,listC)]
    all_pairs.sort(key = lambda p: distance(p[0][0], p[1][0]))
    # make a dict to track which (number, origin_list)s we've already seen
    pairs_by_number_and_list = collections.defaultdict(list)
    min_distance = INFINITY
    min_triplet = None
    # start with the closest pair
    for pair in all_pairs:
        # for the first value of the current pair, see if we've seen that particular
        # (number, origin_list) combination before
        for pair2 in pairs_by_number_and_list[pair[0]]:
            # if so, that means the current pair shares its first value with
            # another pair, so put the 3 unique values together to make a triplet
            this_triplet = (pair[1][0], pair2[0][0], pair2[1][0])
            # check if the triplet agrees more than the previous best triplet
            this_distance = distance(this_triplet)
            if this_distance < min_distance:
                min_triplet = this_triplet
                min_distance = this_distance
        # do the same thing but checking the second element of the current pair
        for pair2 in pairs_by_number_and_list[pair[1]]:
            this_triplet = (pair[0][0], pair2[0][0], pair2[1][0])
            this_distance = distance(this_triplet)
            if this_distance < min_distance:
                min_triplet = this_triplet
                min_distance = this_distance
        # finally, add the current pair to the list of pairs we've seen
        pairs_by_number_and_list[pair[0]].append(pair)
        pairs_by_number_and_list[pair[1]].append(pair)
    return min_triplet

注意：本答案中的所有代码示例都比实际应用时更加详细，以帮助您理解它们的工作原理。但在实际操作中，您会使用更多的列表推导式等语法。

注意2：不能保证代码能够正常运行，但应该可以大致传达思路。

- David Z