Перевернуть / транспонировать карту «один ко многим» в Scala - PullRequest
Новая
       26

Перевернуть / транспонировать карту «один ко многим» в Scala

15 голосов
/ 31 марта 2011

Как лучше всего превратить Map[A, Set[B]] в Map[B, Set[A]]?

Например, как мне превратить 

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

в 

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

(Я использую неизменные коллекции только здесь. И моя настоящая проблема не имеет ничего общего со строками или целыми числами.:)

Ответы [ 6 ]

10 голосов
/ 31 марта 2011

с помощью aioobe и Moritz: 

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

Это немного более читабельно, если вы явно вызываете содержит: 

def reverse[A, B](m: Map[A, Set[B]]) =
  m.values.toSet.flatten.map(v => (v, m.keys.filter(m(_).contains(v)))).toMap
4 голосов
/ 31 марта 2011

Лучшее, что я придумал, это 

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
3 голосов
/ 31 марта 2011

Вот решение с одним утверждением 

 orginalMap
 .map{case (k, v)=>value.map{v2=>(v2,k)}}
 .flatten
 .groupBy{_._1}
 .transform {(k, v)=>v.unzip._2.toSet}

Этот бит довольно аккуратно (*) создает кортежи, необходимые для построения обратной карты 

Map(1 -> Set("a", "b"),
    2 -> Set("b", "c"),
    3 -> Set("c", "d"))
.map{case (k, v)=>v.map{v2=>(v2,k)}}.flatten

производит 

 List((a,1), (b,1), (b,2), (c,2), (c,3), (d,3))

Преобразование этого непосредственно в карту перезаписывает значения, соответствующие дублирующимся ключам, хотя

Добавление .groupBy{_._1} получает это 

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

что ближе. Чтобы превратить эти списки в наборы второй половины пар. 

  .transform {(k, v)=>v.unzip._2.toSet}

дает 

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

QED:)

(*) YMMV

3 голосов
/ 31 марта 2011

Или другой с использованием складок: 

  def reverse2[A,B](m:Map[A,Set[B]])=
      m.foldLeft(Map[B,Set[A]]()){case (r,(k,s)) =>
         s.foldLeft(r){case (r,e)=>
            r + (e -> (r.getOrElse(e, Set()) + k))
         }
      }
1 голос
/ 31 марта 2011

Простое, но, возможно, не супер-элегантное решение: 

  def reverse[A,B](m:Map[A,Set[B]])={
      var r = Map[B,Set[A]]()
      m.keySet foreach { k=>
          m(k) foreach { e =>
            r = r + (e -> (r.getOrElse(e, Set()) + k))
          }
      }
      r
  }
1 голос
/ 31 марта 2011

Самый простой способ, о котором я могу думать, это: 

// unfold values to tuples (v,k)
// for all values v in the Set referenced by key k
def vk = for {
  (k,vs) <- m.iterator
  v <- vs.iterator
} yield (v -> k)

// fold iterator back into a map
(Map[String,Set[Int]]() /: vk) {
// alternative syntax: vk.foldLeft(Map[String,Set[Int]]()) {
  case (m,(k,v)) if m contains k =>
    // Map already contains a Set, so just add the value
    m updated (k, m(k) + v)
  case (m,(k,v)) =>
    // key not in the map - wrap value in a Set and return updated map
    m updated (k, Set(v))
}
...