Scala - 将两个序列组合成连续增加的三元组

Question

解决以下问题的好方法是什么？在命令式风格中，这可以在线性时间内完成。

给定两个已排序的序列 p和 q , f返回一个序列 r (或任何集合)三元组，其中对于每个三元组 (a,b,c)在 r ，以下成立:

( a < b < c )

以下两项中的一项成立:

a , c是两个连续的元素 p , 和 b在 q

a , c是两个连续的元素 q , 和 b在 p

示例:考虑以下两个序列。

val p = Seq(1,4,5,7,8,9)
val q = Seq(2,3,6,7,8,10)

然后 f(p,s)计算以下序列:

Seq((1,2,4), (1,3,4), (5,6,7), (3,4,6), (3,5,6), (8,9,10))

当前解决方案:我不觉得这个很优雅。我正在寻找一个更好的。

    def consecutiveTriplesOneWay(s1: Seq[Int], s2:Seq[Int]) = {
        for {
            i <- 0 until s1.size - 1 if s1(i) < s1(i+1)
            j <- 0 until s2.size if s1(i) < s2(j) &&  s2(j) < s1(i+1)
        } yield (s1(i), s2(j), s1(i+1))
    }

    def consecutiveTriples(s1: Seq[Int], s2:Seq[Int]) =
        consecutiveTriplesOneWay(s1, s2) ++ consecutiveTriplesOneWay(s2, s1)

    def main(args: Array[String]) {
        val p = Seq(1,4,5,7,8,9)
        val q = Seq(2,3,6,7,8,10)

        consecutiveTriples(p, q).foreach(println(_))
    }

编辑:我的命令式解决方案

def consecutiveTriplesOneWayImperative(s1: Seq[Int], s2:Seq[Int]) = {
    var i = 0
    var j = 0
    val triples = mutable.MutableList.empty[(Int,Int,Int)]
    while (i < s1.size - 1 && j < s2.size) {
        if (s1(i) < s2(j) && s2(j) < s1(i + 1)) {
            triples += ((s1(i), s2(j), s1(i + 1)))
            j += 1
        } else if (s1(i) >= s2(j))
            j += 1
        else
            i += 1
    }
    triples.toSeq
}

def consecutiveTriples(s1: Seq[Int], s2:Seq[Int]) = 
    consecutiveTriplesOneWayImperative(s1,s2) ++ 
            consecutiveTriplesOneWayImperative(s2,s1)

Answer 1

命令式解决方案转换为tailrec。有点冗长但有效

def consecutiveTriplesRec(s1: Seq[Int], s2: Seq[Int]) = {
  @tailrec
  def consTriplesOneWay(left: Seq[Int], right: Seq[Int],
                        triples: Seq[(Int, Int, Int)]): Seq[(Int, Int, Int)] = {
    (left, right) match {
      case (l1 :: l2 :: ls, r :: rs) =>
        if (l1 < r && r < l2) consTriplesOneWay(left, rs, (l1, r, l2) +: triples)
        else if (l1 >= r) consTriplesOneWay(left, rs, triples)
        else consTriplesOneWay(l2 :: ls, right, triples)
      case _ => triples
    }
  }
  consTriplesOneWay(s1, s2, Nil) ++ consTriplesOneWay(s2, s1, Nil)
}