Efficient way to identify named Sets with common elements in Scala

Question

Given a Map[String, Set[String]] what is an elegant and efficient way in Scala to determine the set of all pairs of distinct keys where the corresponding sets have a non-empty intersection?

For example fix the map as

  val input = Map (
    "a" -> Set("x", "z"),
    "b" -> Set("f")
    "c" -> Set("f", "z", "44")
    "d" -> Set("99")
  )

then the required output is

  Set(
    ("a", "c"),
    ("b", "c")
  )

Efficient in this context means better than O(n^2) where n is the sum of the number of elements in the family of sets given as input.

ghik ghik · Accepted Answer · 2013-05-30T22:49:01

You can't get better pessimistic complexity than O(n^2). Look at following example:

Map(
  1 -> Set("a"),
  2 -> Set("a"),
  3 -> Set("a"),
  ...
  n -> Set("a")
)

In this case every single pair of sets has non-empty intersection. So the size of output in this case is O(n^2), so you can't get better complexity.

Obviously, that doesn't mean you can't think of better algorithm than just brute force. For example, you could transform this:

val input = Map (
  "a" -> Set("x", "z"),
  "b" -> Set("f")
  "c" -> Set("f", "z", "44")
  "d" -> Set("99")
)

into this:

val transformed = Map (
  "x" -> Set("a"),
  "z" -> Set("a", "c"),
  "f" -> Set("b", "c"),
  "44" -> Set("c"),
  "99" -> Set("d")
)

You can do this in linear time. I'd use Scala collection builders or mutable collections for this to avoid expensive operations on immutable collections.

Then you can just look at every set that is a value in this transformed map and for each one, generate all possible pairs of its elements. This can take O(n^2) but if you don't have many pairs in your output then it will be a lot faster.

Efficient way to identify named Sets with common elements in Scala

1 Answers