如何优雅地实现斯卡拉

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 
} 

Answer 2

我认为这符合你想要的东西的法案。它确实使用了可以重构为另一个匹配语句的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，则会产生此结果。

Answer 3

我完成了这个使用列表的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 4

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 5

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

import scalaz.std.list._ 

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