6

I have a Map[String, List[String]] and I want to invert it. For example, if I have something like

  "1" -> List("a","b","c")
  "2" -> List("a","j","k")
  "3" -> List("a","c")

The result should be

  "a" -> List("1","2","3")
  "b" -> List("1")
  "c" -> List("1","3")
  "j" -> List("2")
  "k" -> List("2")

I've tried this:

  m.map(_.swap)

But it returns a Map[List[String], String]:

  List("a","b","c") -> "1"
  List("a","j","k") -> "2" 
  List("a","c") -> "3"
Kuranes
  • 197
  • 1
  • 12

3 Answers3

9

Map inversion is a little more complicated.

val m = Map("1" -> List("a","b","c")
           ,"2" -> List("a","j","k")
           ,"3" -> List("a","c"))

m flatten {case(k, vs) => vs.map((_, k))} groupBy (_._1) mapValues {_.map(_._2)}
//res0: Map[String,Iterable[String]] = Map(j -> List(2), a -> List(1, 2, 3), b -> List(1), c -> List(1, 3), k -> List(2))

Flatten the Map into a collection of tuples. groupBy will create a new Map with the old values as the new keys. Then un-tuple the values by removing the key (previously value) elements.

jwvh
  • 50,871
  • 7
  • 38
  • 64
  • `flatten`? O_________________________O That's a total abuse of the implicit function argument. If the language wasn't typed, the `flatten` method wouldn't even have an additional implicit conversion argument. It's a trick mostly for satisfying the typechecker, it shouldn't be used to do any non-trivial calculations. – Andrey Tyukin May 30 '18 at 01:37
  • @AndreyTyukin can you provide an alternative? – yishaiz Aug 08 '18 at 14:21
  • 1
    @yishaiz See my answer. – Andrey Tyukin Aug 08 '18 at 15:14
3

An alternative that does not rely on strange implicit arguments of flatten, as requested by yishaiz:

val m = Map(
  "1" -> List("a","b","c"),
  "2" -> List("a","j","k"),
  "3" -> List("a","c"),
)

val res = (for ((digit, chars) <- m.toList; c <- chars) yield (c, digit))
  .groupBy(_._1)          // group by characters
  .mapValues(_.unzip._2)  // drop redundant digits from lists

res foreach println

gives:

(j,List(2))
(a,List(1, 2, 3))
(b,List(1))
(c,List(1, 3))
(k,List(2))
Andrey Tyukin
  • 43,673
  • 4
  • 57
  • 93
  • @yishaiz (and @Andrey), see also [here](https://stackoverflow.com/questions/2338282/elegant-way-to-invert-a-map-in-scala/51356499#51356499). – jwvh Aug 08 '18 at 16:31
  • @jwvh Good. But still, using implicit arguments of `flatten` is a hack. It's clever. But it's a hack ;) – Andrey Tyukin Aug 08 '18 at 16:36
  • I don't disagree. That was only 8 months ago but it feels like a different time/place. – jwvh Aug 08 '18 at 16:43
0

A simple nested for-comprehension may be used to invert the map in such a way that each value in the List of values are keys in the inverted map with respective keys as their values 

implicit class MapInverter[T] (map: Map[T, List[T]]) {
def invert: Map[T, T] = {
  val result = collection.mutable.Map.empty[T, T]

  for ((key, values) <- map) {
    for (v <- values) {
      result += (v -> key)
    }
  }
  result.toMap
}

Usage:

Map(10 -> List(3, 2), 20 -> List(16, 17, 18, 19)).invert
Jeevaraj Dhanaraj
  • 101
  • 3