如何在 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

我认为这符合您的要求。它确实使用了可以重构为另一个匹配语句的 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]] 的 return 类型。*

*我还应该提到第一个有点好，因为 Scala 不介意内部 List[Int] 被隐含，它实际上会产生如果你将第一个案例简单地更改为 Nil => Nil.

Answer 2

我使用 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

正如@Dimitri 指出的那样，如果使用 :: 和 map(._reverse)，复杂性可能会更好。所以，给你……你可以决定:)

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

Answer 3

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

你可以先找到所有的分割点，然后再分割。

Answer 4

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

Answer 5

使用scalaz's groupWhen，相当简单：

import scalaz.std.list._

def increasingSubsequences(xs: List[Int]) = groupWhen(xs)(_ < _)

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

How to implement this simple algorithm elegantly in Scala

functional-programming

scala

list