haskell - 创建采用的路径列表

Question

给定范围(a,b)和行(x,y)，我想构造所有可能的方式来覆盖给定行的范围。

例如，使用范围(0,10)（如果我们将列表过滤为在范围内，则不必担心）和以下列表（对其进行排序使选择下一个值更容易），

list = [(0,1), (1,10), (1,4), (3,5), (5,10)]

我想输出如下涵盖该范围的路径列表，

[
[(0,1), (1,4), (3,5), (5,10)],
[(0,1), (1,10)]
]

我尝试设置以下函数，该函数将获取下一个可能的 (x,y)值的列表，如下所示，但它仅显示单个路径。

-- assume list is sorted based on first pair
nextpaths :: (Num a, Ord a) => [(a, a)] -> ([(a, a)], [(a, a)])
nextpaths ((start, end):xs) = go xs ([], [])
  where go [] acc = acc
        go (y:ys) (next, rest)| fst y <= end = go ys (y:next, rest)
                              | otherwise = (next, y:ys)

paths t@(x:xs) = case nextpaths t of
  ([],_) -> [[x]]
  (n:next, rest) -> map (x:) (paths (n:rest))

我们如何使 paths函数应用于其他 next列表值？

Answer 1

我们可以生成一个最小路径列表：不能删除单个2元组的路径，这样它仍然是有效路径。

通常，在这里处理片段的排序列表会更有效，因为我们可以扫描列表并追加必要的项目。扫描时，我们需要做两件事：我们要覆盖的范围；最后一个范围，这样我们就保证了最小化。

我们首先构造一个函数，假设我们已经选择了一条路径。因此，我们可以定义一个带有签名的函数：

paths1 :: Ord a => (a, a) -> (a, a) -> [(a, a)] -> [[(a, a)]]

如果最后选择的项目大于或等于范围的上限，我们就完成了。在这种情况下，我们返回带有空列表的单例列表。然后，递归调用可以将所选子路径添加到列表中：

paths1 (a, f) (b, c) _ | c >= f = [[]]

如果可能的子范围列表用尽，则无法生成该路径，因此，如果子范围列表为空，我们将返回一个空列表：

paths1 _ _ [] = []

如果我们还没有结束，我们将需要一个额外的子范围。这样的子范围需要满足两个条件：它应该在先前选择的子路径之后开始，并且应该在先前选择的子路径之后结束。因此，我们可以跳过不满足该条件的环境：

paths1 r s@(b, c) ((d, e):xs) | d > c = []
                              | d <= b || e <= c = paths1 r s xs

如果我们可以选择子范围，则可以选择该范围。在这种情况下，我们将更新最后选择的范围，并将所有返回的路径放在前面：

paths1 r s@(_,sb) (x@(_, xb):xs) = map (x:) (paths1 r (sb,xb) xs) ++ paths1 r s xs

现在，我们为 paths1定义了一个完整的实现：

paths1 :: Ord a => (a, a) -> (a, a) -> [(a, a)] -> [[(a, a)]]
paths1 (a, f) (b, c) _ | c >= f = [[]]
paths1 _ _ [] = []
paths1 r s@(b, c) ((d, e):xs) | d > c = []
                              | d <= b || e <= c = paths1 r s xs
paths1 r s@(_,sb) (x@(_, xb):xs) = map (x:) (paths1 r (sb,xb) xs) ++ paths1 r s xs

现在，我们需要实现一个选择第一个子范围的函数。我们可以实现这样的功能 path0：

paths0 :: (a, a) -> [(a, a)] -> [[(a, a)]]

我们应该选择的第一个范围应该在要生成的范围的开始之前和之后开始。因此，我们可以将其实现为：

paths0 :: Ord a => (a, a) -> [(a, a)] -> [[(a, a)]]
paths0 (a, _) ((b, c):_) | b > a || c <= a = []
paths0 r@(a, _) ((_, c):xs) | c <= a = paths0 r xs
paths0 r (x:xs) = map (x:) (paths1 r x xs) ++ paths0 r xs

因此，现在我们可以将两者结合在 path函数中。我们可以首先对列表进行排序，或者将其添加为前提条件：

import Data.List(sort)

paths :: (a, a) -> [(a, a)] -> [[(a, a)]]
paths = (. sort) . paths0

然后，我们获得预期的结果：

Prelude Data.List> paths (0,10) [(0,1), (1,10), (1,4), (3,5), (5,10)]
[[(0,1),(1,4),(3,5),(5,10)],[(0,1),(1,10)]]

以上不是最优雅的解决方案。我将“抛光”作为练习继续进行。