5

我有 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 解决方案，但当然不是内存问题，但已经运行了几个小时，并且卡在第三个元素上。

4

4 回答 4

2

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

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

让您的列表为 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))

您现在正在寻找的是该图中的最小周期。将此答案用于 O(n^3) 算法。（修改后的 Floyd-Warshall 算法）

于 2018-07-02T09:52:28.917 回答
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)

于 2018-07-02T06:38:49.577 回答
0

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

于 2018-07-01T20:38:23.227 回答
0

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

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

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

于 2018-07-02T16:02:41.513 回答