python – 算法,列表元素之间的最近点
我有n个不等大小的排序列表(我事先不知道将会有多少列表).我需要找到每个列表中一个元素之间的最小平均距离. 例如,对于三个列表,给定n = 3:
输出应为(22,24),因为:
这是上例中所有点中最小的一个. 我尝试在Python中实现它如下
我现在怀疑另一部分的实施情况.我想过使用笛卡尔积来生成所有组合但是会遇到内存问题.我的猜测是以某种方式生成所有组合(也许是itertools ??)并循环遍历所有这些但我不知道是否有任何算法可以解决我可以使用的这个问题. 编辑 关于问题的大小,列表的nr最大为100(固定),而元素的nr可以变化,但我会说每个列表中有4或5个点的呈现示例是一个现实场景. 最佳答案
这种方法是一种强力方法,但使用类似于Dijkstra算法的消除方法,这导致了更少的情况(使得算法最有可能快几个数量级,特别是对于大型列表或大量列表).告诉我你是否理解它,我可以澄清一下.可以在此处找到实现:https://github.com/nerryoob/closestPoint
你正在做的是列出不同的数字组合(即答案)?一开始最好(索引0),最后最差,反之亦然,看看效果最好.您将仅为第一个输入列表创建结果列表,完全忽略其他列表.当然,对于一个列表,所有项目都是解决方案 – 它们的总差异为0.所以只需将第一个输入列表复制到结果列表中 接下来,可能使用while循环,请遵循此算法.取最上面的项目并从结果列表中弹出它.存储它的价值.转到下一个输入列表,对于下一个输入列表中的每个项目,复制刚刚弹出的顶部项目,该项目还包含下一个输入列表的项目.找到新的整体差异,并将基于此的新项目插入到列表中.重复,直到顶级解决方案中包含所有列表.这意味着您保证您拥有最佳解决方案(至少是第一个),同时在组合上花费的时间少得多,这显然不是解决方案 >示例( [14,48] 结果列表为[14(0),22(0),36(0),48(0)] >看看14.插入新数字[14和14(0), 继续重复,你最终得到22,24.因为它包含所有n个列表,所以您可以停止并回复答案 要优化它: >删除重复项 编辑: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |