How to implement this simple algorithm elegantly in Scala
I would like to have an elegant implementation of a method with the following (or similar) signature:
def increasingSubsequences(xs: List[Int]): List[List[Int]]
What it does is split the input sequence without reordering the elements, so that each subsequence of the result is strictly increasing.
I implemented it myself like this:
def increasingSubsequences(list: List[Int], temp: List[Int] = Nil, res: List[List[Int]] = Nil): List[List[Int]] = {
(list, temp) match {
case (x :: xs, t :: ts) if t < x => increasingSubsequences(xs, x :: temp, res)
case (x :: xs, Nil) => increasingSubsequences(xs, List(x), res)
case _ if list.nonEmpty => increasingSubsequences(list, Nil, temp.reverse :: res)
case _ if temp.nonEmpty => (temp.reverse :: res).reverse
case _ => res.reverse
}
}
Although the above code is not very long, I would like to see a more elegant and concise solution if possible (using combinators, perhaps).
Example input and output:
List(5, 6, 2, 3, 4, 1, 2, 6, 8, 5) —> List(List(5, 6), List(2, 3, 4), List(1, 2, 6, 8), List(5))
List() —> List()
List(1, 2, 3, 4, 5) —> List(1, 2, 3, 4, 5)
List(5, 4, 3, 2, 1) —> List(List(5), List(4), List(3), List(2), List(1))
source to share
Using scalaz groupWhen , it's pretty simple:
import scalaz.std.list._
def increasingSubsequences(xs: List[Int]) = groupWhen(xs)(_ < _)
source to share
, , . if-else
, , , . , .
def increasingSubsequences(xs: List[Int]): List[List[Int]] = {
xs match {
case Nil => List(Nil) //in case someone calls on empty list
case (head :: Nil) => List(head :: Nil) //base case
case (head :: rest) => {
val finishedRest = increasingSubsequences(rest)
finishedRest match {
case ((headOfFirst :: restOfFirst) :: restOfFinished) => {
if (head < headOfFirst) (head :: headOfFirst :: restOfFirst) :: restOfFinished
else List(List(head), headOfFirst::restOfFirst) ++ restOfFinished
}
}
}
}
}
, :
-
List()
List(List())
-
List(1, 2, 3, 4, 5)
List(List(1, 2, 3, 4, 5)
, , List[List[Int]]
. *
* , , Scala , List[Int]
, , Nil => Nil
.
source to share
I accomplished this with a List foldLeft
:
def increasingSubsequences(list:List[Int]) =
list.foldLeft(List[List[Int]]())((accum, value) => {
accum match {
case Nil => List(List(value))
case headList :: tailList => {
headList match {
case head :: tail if value > head => List(headList :+ value) ++ tailList
case _ => List(List(value)) ++ accum
}
}
}
}).reverse
As @Dimitri pointed out, the complexity MAY be better if you use ::
and map(._reverse)
. So here you go ... you can decide :)
def increasingSubsequences(list:List[Int]) =
list.foldLeft(List[List[Int]]())((accum, value) => {
accum match {
case Nil => List(List(value))
case headList :: tailList => {
headList match {
case head :: tail if value > head => List(value :: headList) ++ tailList
case _ => List(List(value)) ++ accum
}
}
}
}).map(_.reverse).reverse
source to share
def increasingSubsequences(xs: List[Int]): List[List[Int]] = {
val splits = xs.sliding(2).zipWithIndex.toList
.map { case (sub, i) => if (sub(0) >= sub(1)) i + 1 else -1 } filter (_ > 0)
(List(0, splits.head) :: splits.sliding(2).toList ++ List(List(splits.last, xs.size)))
.map { case pos => xs.slice(pos(0), pos(1)) }
}
You can first find all the split points and split them.
source to share