7

我有一个 Pair 列表，它表示具有开始索引和结束索引的行。类型是 (Int,Int) 是两个整数的元组。

例如，现在我希望将任何相互接触的线连接在一起。

List( (1,5),(6,10),(12,20) ) 应该转换为 List( (1,10), (12,20) ) 因为线 (1,5) 接触线 (6,10 ）。只有接触的线连接在一起成为一条线。

我的第一个想法是在列表中使用 foldleft，问题是 foldleft 需要将两个元素转换为一个元素，最终最终只输出一个 (Int,Int)。

第二个想法是我编写的递归解决方案，但这似乎不是最好或最简单的想法。我们采用两个元素，有时输出一个或两个元素的想法似乎应该应用于许多情况，就像 foldleft 一样。

有没有解决这个问题的通用方法或模式或库？

一条线在一维平面上，它不是 ax,y 点。(Int,Int) 是一维平面上的起点和终点。

明确触摸的定义。列表中没有一行重叠，这是一个前提条件，即 (1, 3) 和 (2, 4) 不能存在于列表中，因为它们重叠。

(1,3), (4,5) 可以存在于列表中，因为它们不重叠。

(1,3), (4,5) 确实接触，因为 3 和 4 之间的距离正好为 1。

对于问题 ((1, 5), (6, 10), (6, 12), (13, 15)) 中给出的列表，这是一个无效列表，因为 (6, 10), (6, 12 ) 重叠。

为了您的信息，这是我在这里写这个问题之前的工作代码，您可以看到它不是很好。我只是在使用我构建递归函数的知识来构建结果并返回结果。

  private def joinAtoB(a: LineLike, b: LineLike): LineLike = {
    newFunction(a.start, b.end)
  }

  private def joinTouchingLines(a: LineLike, b: LineLike): Option[LineLike] = {
    if ((a.end + 1) == b.start)
      Some(joinAtoB(a, b))
    else
      None
  }

  @tailrec
  def joinLinesRec(list: List[LineLike], result: List[LineLike] = List[LineLike]())
                     :List[LineLike] = {
    list match {
      case Nil => result
      case item :: Nil => item :: result

      case first :: second :: rest => {
        val joined = joinTouchingLines(first, second)
        val prepend = joined match {
          case None => List(first, second)
          case Some(joinedItem) => List(joinedItem)
        }
        joinLinesRec(rest, prepend ::: result)
      }
    }
  }
4

2 回答 2

5

您可以使用foldRight而不是foldLeft与模仿 cons ( ::) 的二进制函数一起使用，除非相邻元素接触：

def combine(x: (Int, Int), lst: List[(Int, Int)]) = (x, lst) match {
  case (_, Nil) => List(x)
  case ((a, b), (c, d) :: rest) => if (c == b+1)
                                     (a, d) :: rest
                                   else
                                     (a, b) :: lst
}
于 2012-12-29T13:20:38.200 回答
2

使用 foldLeft 执行此操作很简单，但如果您在我们重叠或接触时取出规则部分，则更简单：

def touching(fp: (Int, Int), sp: (Int, Int)) = 
  if (fp._2 >= sp._1) sys.error("Overlap " + fp + " and " + sp) 
  else if (fp._2 == sp._1 - 1) true 
  else false

然后，您可以决定何时要追加以及何时要扩展最后一对：

list.foldLeft(List[(Int,Int)]()){
  (l, p) => 
    if (l.isEmpty || !touching(l.head, p)) p :: l
    else (l.head._1, p._2) :: l.tail
}.reverse
于 2012-12-29T13:16:27.823 回答