创建采用的路径列表 [英] Create list of paths taken

问题描述

鉴于范围(a,b)和第(x,y)行，我想构造所有可能的方法来覆盖给定行的范围.

Given range (a,b) and lines (x,y), I want to construct all the possible ways to cover the range with the given lines.

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

For example with range (0,10) (if we filter list to be within range then we don't have to worry about it) and the following list (sorting it makes easier to pick next value),

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

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

I want to output list of paths taken to cover the range as follows,

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

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

I tried setting up function that would get list of next possible (x,y) values as follows, but it only prints a single path.

-- 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列表值?

How would we make it so that paths functions applies to other next list values?

推荐答案

我们可以生成一个最小路径列表:无法删除单个2元组的路径，使得它仍然是有效路径.

We can generate a list of minimal paths: paths where we can not remove a single 2-tuple such that it is still a valid path.

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

Usually it is more efficient here to work with a sorted list of fragments, since we can scan the list and append items that are necessary. When we scan, we will need two things: the range we want to cover; and the last range, such that we guarantee minimality.

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

We will first construct a function where we assume we already selected a path. We thus can define a function with signature:

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

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

In case the last item selected is greater than or equal to the upperbound of the range, we are done. In that case, we return a singleton list with an empty list. The recursive call can then add the selected subpath to the list:

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

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

In case the list of possible subranges is exhausted, we can not generate such path, we thus return an empty list in case the list of subranges is empty:

paths1 _ _ [] = []

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

In case we have not reached the end yet, we will need an extra subrange. Such subrange needs to satisfy two criteria: it should start after the previously selected subpath, and it should end after the previously selected subpath. We thus can skip suranges that do not satisfy that condition:

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

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

In case we can select the subrange, we thus can pick that one. In that case we thus update the last range selected and will the prepend all the paths that are returned:

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

现在，我们已经为paths1定义了完整的实现:

Now we thus have defined a complete implementation for 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:

We now need to implement a function that selects the first subrange. We can implement such function path0:

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

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

The first range we should select should start before on on the start of the range we want to generate, and after the start of the range. We thus can implement that as:

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函数中.我们可以首先对列表进行排序，或者将其添加为前提条件:

So now we can combine the two in a path function. We can first sort the list, or add this as a pre-condition:

import Data.List(sort)

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

然后我们获得预期的结果:

We then obtain the expected result:

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

以上并不是最优雅的解决方案.我将"抛光"留作进一步练习.

The above is not the most elegant solution. I leave "polishing" it further as an exercise.

这篇关于创建采用的路径列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！