算法，列表元素之间的最近点

Question

我有 n 个大小不等的有序列表（我事先不知道会有多少列表）。我需要找到每个列表中一个元素之间的最小平均距离。

例如，三个列表的 n=3：

a = [14, 22, 36, 48]
b = [14, 23, 30, 72]
c = [1, 18, 24]

输出应该是 (22,23,24) 因为：

mean(abs(22-23), abs(23-24), abs(22-24)) = 1.33333

这是上面例子中所有点中最小的。

我尝试在 Python 中实现如下

def aligner(aoa):
'''
read arrays of arrays of peaks and return closest peaks
'''
#one of arrays is empty
if not [y for x in aoa for y in x]:
    return None
# there is the same nr in all array no need to do anything
candidate = set.intersection(*map(set, aoa))
if candidate:
    # returns intersect
    return [max(list(candidate))] * len(aoa)
else:
    #tried cartesian product via bumpy malloc err
    pass

我现在怀疑的是另一部分的实施。我考虑过使用笛卡尔积来生成所有组合，但遇到了内存问题。我的猜测是以某种方式生成所有组合（也许是 itertools？？）并循环遍历所有这些，但我不知道是否有任何算法可以解决我可以使用的这个问题。

我不需要代码，只是提示是否有任何有效的方法来解决这个问题，或者在置换列表上使用 n 个 for 循环的蛮力是唯一的方法

编辑

关于问题的大小，列表的 nr 最大为 100（固定），而元素的 nr 可以变化，但我会说每个列表有 4 或 5 个点的示例是一个现实的场景。

所有点都是非负的。

尝试了建议的 itertools 解决方案，但当然不是内存问题，但已经运行几个小时了，它卡在第三个元素上。

Answer 1

我不确定找到最佳解决方案的最佳方法，但一种启发式方法可能是检查范围。如果我们的列表已排序，我们可以使用二分查找来检查列表是否包含某个范围内的元素。因此我们可以分而治之，尝试缩小包含每个列表中的元素的范围。由于均值计算的性质，不幸的是，我们可能也对包含许多但不是所有列表中的元素的范围感兴趣，因为非常接近的数字和一些离群值的集合可能会产生较小的差异 - 均值而不是较小范围内的更多变化范围;这使解决方案变得相当复杂。

Answer 2

此方法是一种蛮力方法，但使用了类似于 Dijkstra 算法的消除方法，导致的情况要少得多（使算法最有可能快几个数量级，尤其是对于大列表或大量列表列表）。如果你不明白，告诉我，我可以澄清。可以在此处找到实现：https://github.com/nerryoob/closestPoint

您正在做的是列出不同的数字组合（即答案）？开始时最好（索引 0），最后最差，反之亦然，看看什么最有效。您将为第一个输入列表创建结果列表，完全忽略其他列表。对于一个列表，当然，所有项目都是解决方案 - 它们的总差为 0。因此只需将第一个输入列表复制到结果列表中

接下来，可能有一个 while 循环，遵循这个算法。取出最上面的项目并将其从结果列表中弹出。存储它的值。转到下一个输入列表，对于下一个输入列表中的每个项目，复制您刚刚弹出的顶部项目，该项目也包含下一个输入列表的项目。找到新的整体差异并将基于该差异的新项目插入列表中。重复直到顶部解决方案包含所有列表。这意味着您保证您拥有最佳解决方案（至少联合第一个），同时花费更少的时间在显然不是解决方案的组合上

示例（括号内的数字为总差）

[14, 22, 36, 48] [14, 23, 30, 72] [1, 18, 24]

结果列表是[14(0), 22(0), 36(0), 48(0)]

看14，插入新数[14和14(0), 22(0), 36(0), 48(0)、14 和 23(9)、14 和 30 (16)、14 和 72 (58)]
查看 14 和 14。插入新数字 [22(0)、36(0)、48(0)、14 和 14和18(8)、14和23(9)、14和30(16)、14和14和24(20)、14 和 14 和 1(26), 14 和 72(58)]
查看 22。插入新数字 [36(0), 48(0), 22 和 23(1), 14 以及 14 和 18(8)、22 和 14(8)、22 和 30(8)、14 和 23(9)、14 和 30 (16)、14 和 14 和 24 (20)、14 和 14 和 1(26)、22 和 72(50)、14 和 72(58)]

继续重复，你最终得到 22、23、24。因为其中包含所有 n 列表，因此您可以停下来并返回答案

优化：

删除重复项
也许以某种方式利用有序列表
想想你把总差相同的物品放在哪里，也许数字更多的物品放在第一位

编辑：算法复杂度为 O(n^2)

Answer 3

首先，优化差的均值与优化差的和是一样的。

如果您将问题建模为有向图，则可以解决：

让您的列表为 A、B、C。列表的每个条目都是图的一个顶点 v_ai，其中 a 是列表，i 是索引。

对于 A 中的每个索引 i，B 中的 j，添加一条边 v_ai -> v_bj，权重为 abs(A(i) - B(j))

对于 B 中的每个索引 i，C 中的 j，添加一条边 v_bi -> v_cj，权重为 abs(B(i) - C(j))

对于 C 中的每个索引 i，A 中的 j，添加一条边 v_ci -> v_aj，权重为 abs(C(i) - A(j))

你现在要找的是这个图中的最小周期。将此 answer 用于 O(n^3) 算法。（修改后的 Floyd-Warshall 算法）

Answer 4

我们不太了解您的问题的规模，即有多少列表，每个列表有多少元素。对于初学者和设置基线，您可以只使用 itertools.product 迭代三个列表中元素的所有可能组合，而无需在列表中实现它们。然后您可以迭代这些并找到最好的，或者将它们直接传递给 min 并使用特殊的 key 函数使用 itertools.combinations 和 sum 找到最低的平均距离（如果总和最低，则平均值也最低）。

>>> a = [14, 22, 36, 48]
>>> b = [14, 23, 30, 72]
>>> c = [1, 18, 24]
>>> len(list(itertools.product(a, b, c)))
48
>>> min(itertools.product(a, b, c),
...     key=lambda t: sum(abs(n-m) for n, m in itertools.combinations(t, 2)))
(22, 23, 24)

根据您的问题的大小，这可能太慢了，但也许已经足够了。

算法，列表元素之间的最近点

Algorithm, closest point between list elements

python

python-3.x

algorithm

nested-lists

closest-points