Expand a Set[Set[String]] into Cartesian Product in Scala

Question

I have the following set of sets. I don't know ahead of time how long it will be.

val sets = Set(Set("a","b","c"), Set("1","2"), Set("S","T"))

I would like to expand it into a cartesian product:

Set("a&1&S", "a&1&T", "a&2&S", ..., "c&2&T")

How would you do that?

score 17 · Accepted Answer · answered May 23 '10 at 15:55

17

I think I figured out how to do that.

def combine(acc:Set[String], set:Set[String]) = for (a <- acc; s <- set) yield {
  a + "&" + s 
}

val expanded = sets.reduceLeft(combine)

expanded: scala.collection.immutable.Set[java.lang.String] = Set(b&2&T, a&1&S, 
  a&1&T, b&1&S, b&1&T, c&1&T, a&2&T, c&1&S, c&2&T, a&2&S, c&2&S, b&2&S)

answered May 23 '10 at 15:55

huynhjl

41,520
14
105
158

Synchronicity! In my solution, deferred construction of the Strings until the last step, but they are basically the same. – retronym May 23 '10 at 15:59

score 12 · Answer 2 · answered May 23 '10 at 15:56

12

Nice question. Here's one way:

scala> val seqs = Seq(Seq("a","b","c"), Seq("1","2"), Seq("S","T"))                  
seqs: Seq[Seq[java.lang.String]] = List(List(a, b, c), List(1, 2), List(S, T))

scala> val seqs2 = seqs.map(_.map(Seq(_)))
seqs2: Seq[Seq[Seq[java.lang.String]]] = List(List(List(a), List(b), List(c)), List(List(1), List(2)), List(List(S), List(T)))

scala> val combined = seqs2.reduceLeft((xs, ys) => for {x <- xs; y <- ys} yield x ++ y)
combined: Seq[Seq[java.lang.String]] = List(List(a, 1, S), List(a, 1, T), List(a, 2, S), List(a, 2, T), List(b, 1, S), List(b, 1, T), List(b, 2, S), List(b, 2, T), List(c, 1, S), List(c, 1, T), List(c, 2, S), List(c, 2, T))

scala> combined.map(_.mkString("&"))             
res11: Seq[String] = List(a&1&S, a&1&T, a&2&S, a&2&T, b&1&S, b&1&T, b&2&S, b&2&T, c&1&S, c&1&T, c&2&S, c&2&T)

answered May 23 '10 at 15:56

retronym

54,768
12
155
168

Thanks. I first tried with foldLeft and eventually figured out I needed to use reduceLeft instead (kept getting an empty result). Is the conversion to Seq only necessary to preserve ordering? – huynhjl May 23 '10 at 16:02
Combining at the end will actually be helpful because the sets are in fact in the same space and I need to combine "b&a&a" into "a&b" (remove dups and order the combination). – huynhjl May 23 '10 at 16:10
@huynhjl The use of seq (to begin with) was probably so that retronym could avoid importing `scala.collection.immutable.Set`, and maybe to show that this could be done with the more general interface. – Ken Bloom May 23 '10 at 16:23
`Seq` vs `Set` on the first line doesn't really matter, I just found it easier to use `Seq` to preserve ordering. The choice on the second line does matter, you could use `Set` to remove duplicates, for example. – retronym May 23 '10 at 16:25

score 6 · Answer 3 · answered May 23 '10 at 18:23

6

Came after the batle ;) but another one:

sets.reduceLeft((s0,s1)=>s0.flatMap(a=>s1.map(a+"&"+_)))

answered May 23 '10 at 18:23

Patrick

15,702
1
39
39

score 3 · Answer 4 · edited May 23 '17 at 12:22

3

Expanding on @Patrick's answer. Now it's more general and lazier:

def combine[A](f:(A, A) => A)(xs:Iterable[Iterable[A]]) =
    xs.reduceLeft { (x, y) => x.view.flatMap {a => y.map(f(a, _)) } }

Having it be lazy allows you to save space, since you don't store the exponentially many items in the expanded set; instead, you generate them on the fly. But, if you actually want the full set, you can still get it like so:

val expanded = combine{(x:String, y:String) => x + "&" + y}(sets).toSet

edited May 23 '17 at 12:22

Community

1
1

answered Dec 22 '10 at 22:15

dsg

12,924
21
67
111

Here's a more general solution that allows for an application of map prior to taking the cartesian product: http://stackoverflow.com/a/4515050/244526 – dsg Dec 19 '11 at 06:15

score 3 · Answer 5 · edited May 23 '17 at 12:03

Expanding on dsg's answer, you can write it more clearly (I think) this way, if you don't mind the curried function:

def combine[A](f: A => A => A)(xs:Iterable[Iterable[A]]) =
   xs reduceLeft { (x, y) => x.view flatMap { y map f(_) } }

Another alternative (slightly longer, but much more readable):

def combine[A](f: (A, A) => A)(xs:Iterable[Iterable[A]]) =
   xs reduceLeft { (x, y) => for (a <- x.view; b <- y) yield f(a, b) }

Usage:

combine[String](a => b => a + "&" + b)(sets)   // curried version

combine[String](_ + "&" + _)(sets)             // uncurried version

Expand a Set[Set[String]] into Cartesian Product in Scala

5 Answers5

Linked