list - 如何在 Scala 中优雅地实现这个简单的算法

Question

我想要一个具有以下(或类似)签名的方法的优雅实现:

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

它的作用是分割输入序列而不重新排序元素，以便结果中的每个子序列严格递增。

我自己实现如下:

  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
    }
  }

虽然上面的代码不是很长，但如果可能的话，我希望看到一个更优雅、更简洁的解决方案(可能通过使用组合器)。

示例输入和输出:

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

Answer 1

反转列表，然后使用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
}