David Frank - 1 year ago 98

Scala Question

I would like to have an elegant implementation of the method with the following (or similar) signature:

`def increasingSubsequences(xs: List[Int]): List[List[Int]]`

What it does is it splits the input sequence without reordering the elements so that every subsequence in the result is strictly increasing.

I implemented it myself as follows:

`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 (possibly by using combinators).

`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))

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

Reversing the list and then using `foldLeft`

.

```
def increasingSubsequences(list: List[Int]) = list.reverse.foldLeft(List[List[Int]]()) {
case (a :: as, b) if b < a.head => (b :: a) :: as // same subsequence
case (as, b) => List(b) :: as // new subsequence
}
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**