An elegant way to invert a map in Scala

Question

Studying Scala is currently and you need to invert the map to perform some inverted values ​​-> key searches. I was looking for an easy way to do this, but came up with only:

(Map() ++ origMap.map(kvp=>(kvp._2->kvp._1))) 

Does anyone have a more elegant approach?

Answer 1

Assuming the values ​​are unique, this works:

 (Map() ++ origMap.map(_.swap)) 

In Scala 2.8, however, this is simpler:

 origMap.map(_.swap) 

Being able to do this is part of the reason Scala 2.8 has a new collection library.

Answer 2

Mathematically, the mapping can be irreversible (injective), for example, from Map[A,B] you cannot get Map[B,A] , but instead you get Map[B,Set[A]] , because there can be different keys associated with the same values. So, if you are interested in knowing all the keys, here is the code:

 scala> val m = Map(1 -> "a", 2 -> "b", 4 -> "b") scala> m.groupBy(_._2).mapValues(_.keys) res0: Map[String,Iterable[Int]] = Map(b -> Set(2, 4), a -> Set(1)) 

Answer 3

You can avoid using ._1 when repeating several methods.

Here is one way. This uses a partial function that covers one and only case that matters to the map:

 Map() ++ (origMap map {case (k,v) => (v,k)}) 

Here's another way:

 import Function.tupled Map() ++ (origMap map tupled {(k,v) => (v,k)}) 

A map iteration calls a function with a two-element tuple, and an anonymous function wants two parameters. Function.tupled does the translation.

Answer 4

I came here to find a way to convert a map such as Map [A, Seq [B]] to Map [B, Seq [A]], where each B on the new map is associated with each A to the old map for which B was contained in A -associated sequence.

eg.,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
will turn to
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Here is my solution:

 val newMap = oldMap.foldLeft(Map[B, Seq[A]]().withDefaultValue(Seq())) { case (m, (a, bs)) => bs.foldLeft(m)((map, b) => map.updated(b, m(b) :+ a)) } 

where oldMap is of type Map[A, Seq[B]] , and newMap is of type Map[B, Seq[A]]

The nested foldLefts make me cringe, but this is the easiest way to find this type of inversion. Does anyone have a cleaner solution?

Answer 5

You can invert the map using:

 val i = origMap.map({case(k, v) => v -> k}) 

The problem with this approach is that if your values, which have now become hash keys on your map, are not unique, you will reset duplicate values. To illustrate:

 scala> val m = Map("a" -> 1, "b" -> 2, "c" -> 3, "d" -> 1) m: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 2, c -> 3, d -> 1) // Notice that 1 -> a is not in our inverted map scala> val i = m.map({ case(k , v) => v -> k}) i: scala.collection.immutable.Map[Int,String] = Map(1 -> d, 2 -> b, 3 -> c) 

To avoid this, you can first convert the map to a list of tuples, and then invert so as not to delete duplicate values:

 scala> val i = m.toList.map({ case(k , v) => v -> k}) i: List[(Int, String)] = List((1,a), (2,b), (3,c), (1,d)) 

Answer 6

Okay, so this is a very old question with lots of good answers, but I built a versatile, versatile, Swiss army knife, Map inverter, and this is the place to publish it.

These are actually two inverters. One for individual cost items ...

 //from Map[K,V] to Map[V,Set[K]], traverse the input only once implicit class MapInverterA[K,V](m :Map[K,V]) { def invert :Map[V,Set[K]] = m.foldLeft(Map.empty[V, Set[K]]) { case (acc,(k, v)) => acc + (v -> (acc.getOrElse(v,Set()) + k)) } } 

... and another, very similar, for collections of meanings.

 import scala.collection.generic.CanBuildFrom import scala.collection.mutable.Builder import scala.language.higherKinds //from Map[K,C[V]] to Map[V,C[K]], traverse the input only once implicit class MapInverterB[K,V,C[_]](m :Map[K,C[V]] )(implicit ev :C[V] => TraversableOnce[V]) { def invert(implicit bf :CanBuildFrom[Nothing,K,C[K]]) :Map[V,C[K]] = m.foldLeft(Map.empty[V, Builder[K,C[K]]]) { case (acc, (k, vs)) => vs.foldLeft(acc) { case (a, v) => a + (v -> (a.getOrElse(v,bf()) += k)) } }.mapValues(_.result()) } 

using:

 Map(2 -> Array('g','h'), 5 -> Array('g','y')).invert //res0: Map(g -> Array(2, 5), h -> Array(2), y -> Array(5)) Map('q' -> 1.1F, 'b' -> 2.1F, 'c' -> 1.1F, 'g' -> 3F).invert //res1: Map(1.1 -> Set(q, c), 2.1 -> Set(b), 3.0 -> Set(g)) Map(9 -> "this", 8 -> "that", 3 -> "thus", 2 -> "thus").invert //res2: Map(this -> Set(9), that -> Set(8), thus -> Set(3, 2)) Map(1L -> Iterator(3,2), 5L -> Iterator(7,8,3)).invert //res3: Map(3 -> Iterator(1, 5), 2 -> Iterator(1), 7 -> Iterator(5), 8 -> Iterator(5)) Map.empty[Unit,Boolean].invert //res4: Map[Boolean,Set[Unit]] = Map() 

I would prefer both methods to be in the same implicit class, but the more time I spent studying it, the more problematic it turned out to be.

Answer 7

In scala REPL:

 scala> val m = Map(1 -> "one", 2 -> "two") m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two) scala> val reversedM = m map { case (k, v) => (v, k) } reversedM: scala.collection.immutable.Map[java.lang.String,Int] = Map(one -> 1, two -> 2) 

Please note that duplicate values ​​will be overwritten by the latest addition to the map:

 scala> val m = Map(1 -> "one", 2 -> "two", 3 -> "one") m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two, 3 -> one) scala> val reversedM = m map { case (k, v) => (v, k) } reversedM: scala.collection.immutable.Map[java.lang.String,Int] = Map(one -> 3, two -> 2) 

Answer 8

Starting with Scala 2.13 , to swap keys / values ​​without losing keys associated with the same values, we can use the Map new K) method (f: A => B): scala.collection.immutable.Map [K, CC [ B]] rel = "nofollow noreferrer"> groupMap , which (as its name implies) is the equivalent of groupBy and ping map grouped elements.

 Map(1 -> "a", 2 -> "b", 4 -> "b").groupMap(_._2)(_._1) // Map("b" -> List(2, 4), "a" -> List(1)) 

It:

• group elements based on their second part of the tuple ( _._2 ) (group part of the group map)

• map grouped elements, taking their first part of the tuple ( _._1 ) (part of the map of the Map group)

This can be seen as a one-pass version of map.groupBy(_._2).mapValues(_.map(_._1)) .

Answer 9

• The converse is a better name for this operation than the converse (as in the “inverse mathematical function”)

• I often do this inverse transformation not only on maps, but also on other (including Seq) collections. I believe that it is better not to limit the definition of my reverse operation to one-to-one maps. Here's the definition I'm working with for maps (please suggest improvements to my implementation).

   def invertMap[A,B]( m: Map[A,B] ) : Map[B,List[A]] = { val k = ( ( m values ) toList ) distinct val v = k map { e => ( ( m keys ) toList ) filter { x => m(x) == e } } ( k zip v ) toMap } 

If this is a one-to-one map, you get lists of single items that can be trivially checked and converted to map [B, A], and not map [B, list [A]].

Answer 10

We can try using this foldLeft function, which takes care of collisions and inverts the map in one pass.

 scala> def invertMap[A, B](inputMap: Map[A, B]): Map[B, List[A]] = { | inputMap.foldLeft(Map[B, List[A]]()) { | case (mapAccumulator, (value, key)) => | if (mapAccumulator.contains(key)) { | mapAccumulator.updated(key, mapAccumulator(key) :+ value) | } else { | mapAccumulator.updated(key, List(value)) | } | } | } invertMap: [A, B](inputMap: Map[A,B])Map[B,List[A]] scala> val map = Map(1 -> 2, 2 -> 2, 3 -> 3, 4 -> 3, 5 -> 5) map: scala.collection.immutable.Map[Int,Int] = Map(5 -> 5, 1 -> 2, 2 -> 2, 3 -> 3, 4 -> 3) scala> invertMap(map) res0: Map[Int,List[Int]] = Map(5 -> List(5), 2 -> List(1, 2), 3 -> List(3, 4)) scala> val map = Map("A" -> "A", "B" -> "A", "C" -> "C", "D" -> "C", "E" -> "E") map: scala.collection.immutable.Map[String,String] = Map(E -> E, A -> A, B -> A, C -> C, D -> C) scala> invertMap(map) res1: Map[String,List[String]] = Map(E -> List(E), A -> List(A, B), C -> List(C, D))