Reverse / transpose a one-to-many map in Scala

Question

What is the best way to turn a Map[A, Set[B]] into a Map[B, Set[A]]?

For example, how do I turn a

Map(1 -> Set("a", "b"),
    2 -> Set("b", "c"),
    3 -> Set("c", "d"))

into a

Map("a" -> Set(1),
    "b" -> Set(1, 2),
    "c" -> Set(2, 3),
    "d" -> Set(3))

(I'm using immutable collections only here. And my real problem has nothing to do with strings or integers. :)

Answer 1

with help from aioobe and Moritz:

def reverse[A, B](m: Map[A, Set[B]]) =
  m.values.toSet.flatten.map(v => (v, m.keys.filter(m(_)(v)))).toMap

It's a bit more readable if you explicitly call contains:

def reverse[A, B](m: Map[A, Set[B]]) =
  m.values.toSet.flatten.map(v => (v, m.keys.filter(m(_).contains(v)))).toMap

Answer 2

Best I've come up with so far is

val intToStrs = Map(1 -> Set("a", "b"),
                    2 -> Set("b", "c"),
                    3 -> Set("c", "d"))

def mappingFor(key: String) =
    intToStrs.keys.filter(intToStrs(_) contains key).toSet

val newKeys = intToStrs.values.flatten
val inverseMap = newKeys.map(newKey => (newKey -> mappingFor(newKey))).toMap