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

Question

初学者的问题。给定一个任意长度为的列表，其中包含一个或多个字符（如List（“ab”，“def”，“t”））中的一个或多个字符，如何生成包含所有组合的列表？防爆。列表（“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

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

Answer 3

这被称为sequence一个操作，即更普遍变成一个F[G[A]]为G[F[A]]（你需要了解F和G - 见this answer或this blog post的更详细一些事情）。

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