我试图从我的作业中回答这个问题：
给定任意
foo :: [[a]] -> ([a], [a])，写出函数foo满足的一条定律，涉及map到列表和对。
一些背景：我是一名学习函数式编程课程的一年级本科生。虽然这门课程比较入门，但讲师在教学大纲中提到了很多东西，其中包括自由定理。因此，在尝试阅读 Wadler 的论文后，我认为concat :: [[a]] -> [a]with the lawmap f . concat = concat . map (map f)看起来与我的问题相关，因为我们必须具有foo xss = (concat xss, concat' xss)whereconcat和concat'are 类型的任何函数[[a]] -> [a]。然后foo满足bimap (map f, map g) . foo = \xss -> ((fst . foo . map (map f)) xss, (snd . foo . map (map g)) xss) …
假设我们有两个长度相同的列表，ls1和ls2。例如，我们有
ls1 = [4, 6]
ls2 = [3, 5]
并为每个元件中ls1，我们有与一个元件与一个元素配对它ls2，以这样的方式，使得总（绝对在元件之间）的差异ls1，并在元件ls2是最小的。一个元素只能匹配一次。在上面的例子中，最佳的方式是匹配4是ls1用3在ls2，并5在ls1与6中ls2，其产生的总差
(4 - 3) + (6 - 5) = 2
我需要一个程序来返回这两个列表中的元素之间的最小总差。列表的长度是任意的，列表中元素的值也是任意的（但它们都是正整数）。
我目前知道，使用置换暴力破解解决方案是一个选择，但是我需要的是具有最佳时间和空间复杂度的代码。我听说过动态编程的概念，但是我不知道该如何实现它。预先感谢您的答复。
附言 这是我当前使用置换的蛮力代码，在运行时或内存使用方面效率不高：
from itertools import permutations
def minimum_total_difference(ls1, ls2):
length = len(ls1)
possibilities = list(permuations(ls1, length))
out = 10**10
for possibility in possibilities:
out_ = 0
for _ in …我想根据2D平面上一组点之间的欧氏距离计算最小生成树.我当前的代码存储了所有边,然后执行Prim的算法以获得最小的生成树.但是,我知道这样做会O(n^2)占用所有边缘的空间.
在做了一些研究之后,如果我首先在这组点上计算delaunay三角剖分,然后通过在三角剖分的边缘上运行Prim或Kruskal算法来获得最小生成树,那么很明显可以优化内存和运行时.
这是编程竞赛的一部分(https://prologin.org/train/2017/qualification/taxi_des_neiges),所以我怀疑我能否使用scipy.spatial.有没有其他方法可以简单地获得Delaunay三角剖分中包含的边缘？
提前致谢.