scala中一系列数字的子序列

Question

例如我有：List(1,3,2,5)

我如何得到所有这些：List(1), List(3), List(2), List(5), List(1,3), List(1,2), List(1,5), List(3,2), List(3,5), List(2,5), List(1,3,2), List(1,3,5), List(1,2,5), List(3,2,5), List(1,3,2,5))

我需要这个用于最长增加子序列 - 问题，例如这个答案是：（1,3,5）

我希望将它用于更大的列表。

Answer 1

你想要从1到阵列长度的所有combinations()。

val arr = Array(4, 3, 1)

arr.indices.flatMap(x => arr.combinations(x + 1))
//res0: Seq[Array[Int]] = Vector(Array(4), Array(3), Array(1), Array(4, 3), Array(4, 1), Array(3, 1), Array(4, 3, 1))

---

更新

这将为您提供所有可能的组合，保留原始订单和重复元素。

def subseqs[A](seq :Seq[A]) :List[Seq[A]] = seq match {
  case hd +: tl =>
    val res = subseqs(tl)
    Seq(hd) :: res ++ res.map(hd +: _)
  case Seq() => Nil
}

结果是n ^ 2-1的List可能的子序列。因此，对于8个元素的集合，您将获得255个子序列。

当然，这对于您的目的来说太单调乏味且效率低下。生成所有可能的子序列以找到最长的增加有点像洗你附近的所有衣服，所以你早上会有干净的袜子。

更好的是只生成增加的子序列并从该集合中找到最长的子代码（9行代码）。

Answer 2

[更新以回应更新的问题]

[感谢@jwvh在原始版本中发现错误]

此方法将生成List的所有可能的子序列：

def subsequences[T](list: List[T]): List[List[T]] =
  list match {
    case Nil =>
      List(List())
    case hd :: tl =>
      val subs = subsequences(tl)

      subs.map(hd +: _) ++ subs
  }

请注意，由于多种原因，这种方法效率不高，因此它不是解决“增长最长的子序列问题”的好方法。

---

[原始答案]

此函数将生成任何序列的所有非空连续子序列：

 def subsequences[T](seq: Seq[T]) =
   seq.tails.flatMap(_.inits).filter(_.nonEmpty)

这将返回一个Iterator，以便依次创建每个子序列，从而减少内存使用量。

请注意，与使用combinations或Set的解决方案不同，这将生成所有子序列并将保留值的顺序。

---

你可以在你的“增长最快的子序列问题”中使用它，如下所示：

def isAscending(seq: Seq[Int]): Boolean =
  seq.length <= 1 || seq.sliding(2).forall(x => x(0) < x(1))

subsequences(a).filter(isAscending).maxBy(_.length)

结果将是输入a中最长的升序值序列。