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?

Goosy

Answer 1

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)

Goosy

Synchronicity! In my solution, deferred construction of the Strings until the last step, but they are basically the same. – Halima

Answer 2

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)

Halima

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? – Goosy

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). – Goosy

@Goosy 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. – Lactobacillus

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. – Halima

Answer 3

Came after the batle ;) but another one:

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

Bowery

Answer 4

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

Mehala

Here's a more general solution that allows for an application of map prior to taking the cartesian product: https://mcmap.net/q/104044/-cartesian-product-and-map-combined-in-scala – Mehala

Answer 5

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

Stocking