how to generate string combinations from a list of strings?

Question

Beginner question. Given a list of arbitrary length that contains one or more characters in a string such as List("ab", "def", "t"), how do you generate a list containing all the combinations? Ex. List("adt", "aet", "aft", "bdt", ...) Thanks in advance.

Answer 1

A simple recursive method could look like this:

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
}

Beware that this method is NOT tail recursive, so it will overflow for long lists.

Answer 2

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

Answer 3

This is an operation called sequence that more generally turns a F[G[A]] into a G[F[A]] (you need to know certain things about F and G—see this answer or this blog post for more detail).

With Scalaz, for example, you can write this:

import scalaz._, Scalaz._

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

Or equivalently:

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

And you'll get the following, as expected:

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

This isn't much more concise than the standard-library version with foldLeft, but sequence is a useful abstraction to know about.

Answer 4

Just starting with Scala myself but you can use 'subsets' method to do most of the work for you:

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)

which gives you:

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)