0

我们如何根据相邻元素之间的差异在 scala 中拆分列表。例如，给定 List(1,3,6,10,12,14) 和差异 3，该函数将返回 List(List(1,3),List(6),List(10,12,14))。

我们可以使用 foldLeft 来做到这一点吗？我试图创建一个函数

def splitDiff(list:List[Int],diff:Int) = 
     def func(list:List[List[Int]],m:Int):List[List[Int]] = //compare with last element
     list.foldLeft(List(List(0))).foldLeft(func)

但是内部函数似乎很难？有什么帮助吗？

4

4 回答 4

2

嗯，我有一个解决方案，但我怀疑可以做得更好：

(test.head :: test).sliding(2).toList.map( (pair: List[Int]) => (pair(1), pair(1) - pair(0)) )
                   .foldLeft(List(List.empty[Int])){ (acc, pair) => 
     if (pair._2 < 3) (pair._1 :: acc.head) :: acc.tail else List(pair._1) :: acc }

请注意，这会以“双重反转”的顺序给出结果：

res3: List[List[Int]] = List(List(14, 12, 10), List(6), List(3, 1))

可以通过添加.map(_.reverse).reverse到函数的末尾来纠正。

编辑- 替代尝试：

def func(is: List[Int], diff: Int): List[List[Int]] = {
  def loop(is: List[Int], prev: Int, acc: List[List[Int]]): List[List[Int]] = is match {
    case Nil => acc
    case h :: t if (h - prev < diff) => loop(t, h, (h :: acc.head) :: acc.tail)
    case h :: t => loop(t, h, List(h) :: acc)
  }

  loop(is, is.head, List(List.empty[Int]))
}

再次，以双重反转形式给出解决方案。

于 2013-10-26T10:45:22.110 回答
1

使用 foldLeft 的另一种解决方案：

scala> val x = List(1,3,6,10,12,14)
x: List[Int] = List(1, 3, 6, 10, 12, 14)

scala> val y = x.foldLeft((x.head,List[Int](),List[List[Int]]())) 
     ((x,y)=> if((y- x._1) <3) (y,y :: x._2,x._3) else (y,List(y), x._2 :: x._3))
y: (Int, List[Int], List[List[Int]]) = (14,List(14, 12, 10),List(List(6), List(3
, 1)))

scala> val ans = y._2 :: y._3
ans: List[List[Int]] = List(List(14, 12, 10), List(6), List(3, 1))
于 2013-10-26T10:56:23.600 回答
0

请记住，这是未经测试的：

  def splitListDiff(li: List[Int], diff: Int): List[Int] =
        {
          li match {
            case hd :: tl => if (hd - tl < diff) hd :: splitListDiff(tl, diff) else return li ++ splitListDiff(tl, diff)
            case _ => return li
          }
        }

但是您想要一个利用 foldleft 的解决方案？

于 2013-10-26T10:50:53.353 回答
0

以下作品无需额外反转。由于 OP 没有说明列表的元素是否始终按升序排列，我认为使用它Math.abs也很好：

def splitDiff(diff: Int)(xs: List[Int]): List[List[Int]] = xs match {
  case Nil      => Nil
  case h :: t   =>
    val head = h :: ((xs zip t) takeWhile {
      case (a,b) => Math.abs(b-a) < diff
    } map (_._2))
    head :: splitDiff(diff)(xs drop head.length)
}

这种方法的缺点是尾巴会一遍又一遍地拉上拉链。但是，可以通过封装匹配项并在开始时仅压缩一次来轻松避免这种情况。

于 2013-10-27T07:08:42.547 回答