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

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解决方案,但当然不是内存问题,但已经运行了几个小时并且坚持第3个元素.

Answer 1

此方法是一种强力方法，但使用类似于 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)