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

similar, except for sets: http://stackoverflow.com/q/11581175/770361 — Luigi Plinge, Oct 29 '12 at 05:34

Kim Stebel · Accepted Answer · 2012-10-28T17:53:26.010

95

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

edited Oct 28 '12 at 17:53

answered Oct 28 '12 at 15:00

Kim Stebel

41,826
12
125
142

4

I think it is really a clean approach to solve a complicated problem – Shakti Oct 28 '12 at 16:20
18

Unless there is repetition in numbers. – Chetan Bhasin Sep 17 '14 at 16:26
Unless there are some heavy data structures in a list, making toSet (hashing) extremely slow. – Rok Kralj Dec 20 '14 at 14:18
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 – ericpeters Feb 16 '16 at 21:11
1

@ericpeters It says "combinations" not "permutations" so order is not important ;) – Carlos Verdes Jul 13 '16 at 04:50

score 35 · Answer 2 · answered Oct 28 '12 at 21:13

35

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

answered Oct 28 '12 at 21:13

pagoda_5b

7,333
1
27
40

True. But the way I used to do this was waaaay hairier =P – Tiago Farias May 12 '13 at 05:42
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](http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List@combinations(n:Int):Iterator[Repr]) – pagoda_5b Jul 25 '16 at 19:22

score 10 · Answer 3 · answered Oct 28 '12 at 15:47

10

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.

answered Oct 28 '12 at 15:47

Santosh Gokak

3,393
3
22
24

score 9 · Answer 4 · answered Oct 28 '12 at 14:38

9

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.

answered Oct 28 '12 at 14:38

Science_Fiction

3,403
23
27

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

4 Answers4

Linked