Zyga Zyga - 1 year ago 71
Scala Question

Collapse the list of sets based on common element

I have something that looks like an easy enough problem that I wanted to solve functionally using Scala but cannot figure it out.
I am learning Scala and want to make sure that its done using functional programming principles. Below piece of code (which doesnt even work...) is all I managed and
it still has a mutable variable...
Any help is appreciated.

Basically I have a list of sets and I want to join all the sets that has common elements.
And apply that recursively, i.e. keep joining the sets in the list until they are only disjointed ones left.

So for input

List(Set(1,2,3), Set(4,1,5), Set(6,2,7), Set(8,9))
I want to get
List(Set(1,2,3,4,5,6,7), Set(8,9))

My code below - again it doesnt fully work.

def mergeSets(sets: List[Set[Int]]): List[Set[Int]] = {
def go(list: List[Set[Int]], result: List[Set[Int]]): List[Set[Int]] = list match {
case Nil => result
case h :: t => {
var tmpResult = result
tmpResult = list.filter(_.intersect(h).nonEmpty).map(_ ++ h) ::: result
tmpResult = list.filter(_.intersect(h).isEmpty) ::: tmpResult
go(t, tmpResult.toSet.toList)
go(sets, List())

Answer Source

Here is the "one line" solution that combines higher order functions to get the desired result:

val l = val l = List(Set(1,2,3), Set(4,1,5), Set(6,2,7), Set(8,9))
(for (el <- l) yield 
     l.foldLeft(el)((s, x) =>
            if (s.intersect(x).size > 0) s.union(x) else s)

The main ideas is iterate over every set and yield the union of all the appropriate sets. The only trick here is using of toSet in order to remove duplicates.