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

93

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,194
12
122
141

4

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

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,165
1
27
38

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 ` – pagoda_5b Jul 25 '16 at 19:22

score 9 · Answer 3 · 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,323
20
26

score 9 · Answer 4 · answered Oct 28 '12 at 15:47

9

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,243
3
20
23

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

4 Answers4

Linked