如何從字符串列表中生成字符串組合？

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)