Haskell 中数字列表的成对距离

Question

如果X是一组数字，那么ΔX是multiset组数字，表示每2个数字之间的两两相减。例如，如果 X 是一条直线上按升序排列的一组点，那么 ΔX 就是这些点之间成对距离的多重集。如何为数字列表编写 returns 成对距离的函数？下面的工作，但我想要一个更优雅的解决方案。如果可能，请包括理论或直觉，它们可能会提供有关如何解决类似问题的见解。

pairwise_distances :: [Int] -> [Int]
pairwise_distances [] = []
pairwise_distances [x] = []
pairwise_distances (x:xs) = sort $ map (abs . (x-)) xs ++ pairwise_distances xs

pairwise_distances [3,2,1] -- [1,1,2]
pairwise_distances [0,2,4,7,10] -- [2,2,3,3,4,5,6,7,8,10]

Answer 1

一种选择是将成对列表的生成与差异计算分开

abs_distance x y = abs (x - y)

pairs []     = []
pairs (x:xs) = map (\y -> (x,y)) xs ++ pairs xs
-- or, with TupleSections enabled,
-- pairs (x:xs) = map (x,) xs ++ pairs xs

这样你就可以写

pairwise_distances = sort . map (uncurry abs_distance) . pairs

这当然更干净（而且，我认为，更优雅），尽管它可能不是您正在寻找的那种优雅。

Answer 2

distances xs = sort [ y - x | (x:ys) <- tails (sort xs), y <- ys ]

直觉：这个想法是生成 xs 中的所有不同元素对。每个元素在列表中都有一些位置。如果我们把 x 放在列表的 y 之前，那么 x 是列表尾部的头部，而 y 是尾部的某处.如果先排序 xs，然后排序 y >= x。你可以在最后取 abs (y-x) 而不是排序 xs.

Answer 3

它的拼写和听起来一样。

 f xs = [x-x' | x <- xs, x' <- xs]

这当然会使每对计数两次，一次按顺序，一次按倒序，所以一半的距离将为负数。根据您的具体需要，您可以使用此工具或以下工具之一：

f xs = [abs(x-x') | x <- xs, x' <- xs]

f xs = [x-x' | x <- xs, x' <- xs, x>x']

后者依赖于 xs 是一个集合，即其中没有重复点，并且没有应包含在答案中的零距离。

Haskell 中数字列表的成对距离

Pairwise distances of a list of numbers in Haskell

haskell

combinatorics