CODEWITHSUNDEEP
scaladictionary
Anshu Jain
Anshu Jain

Reputation: 43

How to compute inverse of a multi-map

I have a Scala Map: x: [b,c] y: [b,d,e] z: [d,f,g,h]

I want inverse of this map for look-up. b: [x,y] c: [x] d: [x,z] and so on.

Is there a way to do it without using in-between mutable maps

If its not a multi-map - Then following works:

typeMap.flatMap { case (k, v) => v.map(vv => (vv, k))}

Upvotes: 4

Views: 227

Answers (2)

vossad01
vossad01

Reputation: 11948

Here is my simplification as a function:

def reverseMultimap[T1, T2](map: Map[T1, Seq[T2]]): Map[T2, Seq[T1]] =
  map.toSeq
    .flatMap { case (k, vs) => vs.map((_, k)) }
    .groupBy(_._1)
    .mapValues(_.map(_._2))

The above was derived from @Diego Martinoia's answer, corrected and reproduced below in function form:

def reverseMultimap[T1, T2](myMap: Map[T1, Seq[T2]]): Map[T2, Seq[T1]] = {
  val instances = for {
    keyValue <- myMap.toList
    value <- keyValue._2
  } yield (value, keyValue._1)

  val groupedLookups = instances.groupBy(_._1)
  val reverseLookup = groupedLookups.map(kv => kv._1 -> kv._2.map(_._2))
  reverseLookup
}

Upvotes: 0

Diego Martinoia
Diego Martinoia

Reputation: 4662

EDIT: fixed answer to include what Marth rightfully pointed out. My answer is a bit more lenghty than his as I try to go through each step and not use the magic provided by flatMaps for educational purposes, his is more straightforward :)

I'm unsure about your notation. I assume that what you have is something like:

val myMap = Map[T, Set[T]] (
  x -> Set(b, c),
  y -> Set(b, d, e),
  z -> Set(d, f, g, h)
)

You can achieve the reverse lookup as follows:

val instances = for {
  keyValue <- myMap.toList
  value <- keyValue._2
}
yield (value, keyValue._1)

At this point, your instances variable is a List of the type:

(b, x), (c, x), (b, y) ...

If you now do:

val groupedLookups = instances.groupBy(_._1)

You get:

b -> ((b, x), (b, y)),
c -> ((c, x)),
d -> ((d, y), (d, z)) ...

Now we want to reduce the values so that they only contain the second part of each pair. Therefore we do:

val reverseLookup = groupedLookup.map(_._1 -> _._2.map(_._2))

Which means that for every pair we maintain the original key, but we map the list of arguments to something that only has the second value of the pair.

And there you have your result.

(You can also avoid assigning to an intermediate result, but I thought it was clearer like this)

Upvotes: 5

Related Questions