CODEWITHSUNDEEP
scalacollections
Michael
Michael

Reputation: 42050

How to split a sequence by a subsequence?

Suppose I've got a sequence of integers and need to split it by a subsequence like this:

def splitBySeq(xs: Seq[Int], ys: Seq[Int]): (Seq[Int], Seq[Int]) = ???

val xs = List(1, 2, 3, 4, 5)
splitBySeq(xs, Nil)                 // (List(1, 2, 3, 4, 5), Nil)
splitBySeq(xs, List(1))             // (Nil, List(2, 3, 4, 5))
splitBySeq(xs, List(5))             // (List(1, 2, 3, 4), Nil)
splitBySeq(xs, List(3, 4))          // (List(1, 2), List(5))
splitBySeq(xs, List(11, 12))        // (List(1, 2, 3, 4, 5), Nil)
splitBySeq(xs, List(1, 2, 3, 4, 5)) // (Nil, Nil)

If ys is a a subsequence of xs then the function should return a pair of sequences -- xs1 and xs2, so that xs1 ++ ys ++ xs2 == xs. Otherwise the function returns xs.

How would you implement splitBySeq ?

Upvotes: 2

Views: 168

Answers (2)

Krzysztof Atłasik
Krzysztof Atłasik

Reputation: 22595

Another solution, with tail-recursive function doing one iteration:

def splitBySeq[A](xs: Seq[A], ys: Seq[A]): (Seq[A], Seq[A]) = {

  @tailrec
  def go(a: List[A], b: List[A], acc: List[A], rest: List[A]): (Seq[A], Seq[A]) = {

    (a, b) match {
      case (z :: zs, w :: ws)  => {
        if(z == w) {
          go(zs, ws, z :: acc, rest)
        } else{
          go(zs, ys.toList, Nil, z :: (acc ++ rest))
        }
      }
      case (zs, Nil) => (rest.reverse, zs)
      case (Nil, _) => (rest.reverse, Nil)
    }
  }

  if(ys.isEmpty) {
    (xs, Nil)
  } else {
    go(xs.toList, ys.toList, Nil, Nil)
  }

}

Upvotes: 3

jwvh
jwvh

Reputation: 51271

This appears to get at what you're after.

def splitBySeq(xs: Seq[Int], ys: Seq[Int]): (Seq[Int], Seq[Int]) = {
  val idx = xs indexOfSlice ys
  if (idx < 0) (xs, Nil)
  else {
    val (a,b) = xs splitAt idx
    (a, b drop ys.length)
  }
}

Note that in the 1st test case, splitBySeq(xs, Nil), the result seqs are switched because Nil matches the zero index of any Seq.

Upvotes: 3

Related Questions