scala - 如何从字符串列表中生成字符串组合？

Question

初学者问题。给定一个任意长度的列表，其中包含字符串中的一个或多个字符，例如 List("ab", "def", "t")，如何生成包含所有组合的列表？前任。List("adt", "aet", "aft", "bdt", ...) 提前致谢。

Answer 1

一个简单的递归方法可能如下所示：

def foo(xs: List[String], current: String = ""): List[String] = xs match {
  case head :: Nil =>
    head map { c =>
      current + c
    } toList

  case head :: tail =>
    head flatMap { c =>
      foo(tail, current+c)
    } toList

  case _ => Nil
}

请注意，此方法不是尾递归的，因此对于长列表它会溢出。

Answer 2

这是一个被称为sequence更普遍地将 aF[G[A]]转换为 a 的操作G[F[A]]（您需要了解有关Fand的某些事情 - 请G参阅此答案或此博客文章以获取更多详细信息）。

例如，使用Scalaz，您可以这样写：

import scalaz._, Scalaz._

List("ab", "def", "t").map(_.toList).sequence.map(_.mkString)

或等效地：

List("ab", "def", "t").traverse(_.toList).map(_.mkString)

正如预期的那样，您将获得以下信息：

List(adt, aet, aft, bdt, bet, bft)

这并不比带有 的标准库版本简洁得多foldLeft，但sequence它是一个有用的抽象知识。

Answer 3

List("ab", "def", "t").foldLeft(List("")){ (acc, s) =>
  for(prefix <- acc; c <- s) yield (prefix + c)
}

Answer 4

我自己刚开始使用 Scala，但您可以使用“子集”方法为您完成大部分工作：

val lst = List("ab", "def", "t")
val re = (for(l <- lst) yield (l.toCharArray)).flatten.toSet.subsets.toList
val res = for(r <- re) yield (r.mkString)

这给了你：

res: List[String] = List("", e, t, f, a, b, d, et, ef, ea, eb, ed, tf, ta, tb, t
  d, fa, fb, fd, ab, ad, bd, etf, eta, etb, etd, efa, efb, efd, eab, ead, ebd, t
  fa, tfb, tfd, tab, tad, tbd, fab, fad, fbd, abd, etfa, etfb, etfd, etab, etad,
   etbd, efab, efad, efbd, eabd, tfab, tfad, tfbd, tabd, fabd, etfab, etfad, etf
  bd, etabd, efabd, tfabd, etfabd)