How to create all possible combinations from the elements of a list?

Question

I have the following list:

List(a, b, c, d, e)

How to create all possible combinations from the above list?

I expect something like:

a
ab
abc 

Solution 1

Or you could use the subsets method. You'll have to convert your list to a set first though.

scala> List(1,2,3).toSet[Int].subsets.map(_.toList).toList
res9: List[List[Int]] = List(List(), List(1), List(2), List(3), List(1, 2), List(1, 3), List(2, 3), List(1, 2, 3))

Solution 2

def combine(in: List[Char]): Seq[String] = 
    for {
        len <- 1 to in.length
        combinations <- in combinations len
    } yield combinations.mkString 

Solution 3

def powerset[A](s: Set[A]) = s.foldLeft(Set(Set.empty[A])) { case (ss, el) => ss ++ ss.map(_ + el) }

Sounds like you need the Power set.

Solution 4

val xs = List( 'a', 'b' , 'c' , 'd' , 'e' )
(1 to xs.length flatMap (x => xs.combinations(x))) map ( x => x.mkString(""))

This should give you all the combination concatenated by empty String.

View more solutions

Comments

[Shakti]

I think it is really a clean approach to solve a complicated problem

[Tiago Farias]

True. But the way I used to do this was waaaay hairier =P

[Chetan Bhasin]

Unless there is repetition in numbers.

[Rok Kralj]

Unless there are some heavy data structures in a list, making toSet (hashing) extremely slow.

[ericpeters]

Also, if you are trying to do do anything where ordering matters (checking for a part number that has a delimiter in the terms/etc), converting to a set will kill that information too

[Carlos Verdes]

@ericpeters It says "combinations" not "permutations" so order is not important ;)

[pagoda_5b]

The method combinations(length) defined on List, gives you back a further iterator of sublists of limited length generated by combining the elements of the original list in any possible way. The for comprehension gives you all possible combinations for all lengths between 1 and the whole original list's length. The combinations assigned on the left of <- is one such possible shuffle. The yield gives you back a List of all those possible combinations. Check the docs