嵌套数据结构的通用转换

Question

我想将两种转换应用于某些嵌套数据结构：

1. Map> 转换为 Map>

例如：

Map.of("a", Map.of("X", 1, "Y", 2), 
       "b", Map.of("Y", 3))

应该转化为

Map.of("X", Map.of("a", 1),
       "Y", Map.of("a", 2, "b", 3))

2. Map 转换为 Map

例如：

Map.of("a", Set.of("X", "Y"), 
       "b", Set.of("Y", "Z"))

应该转化为

Map.of("X", Set.of("a"),
       "Y", Set.of("a", "b"),
       "Z", Set.of("b"))

我不知道这些转换的名称，也没有在我使用的任何 JVM 语言（主要是 Java，有时是 Groovy 和 Clojure）中找到它们的实现，可能是因为我不知道要寻找什么. 它们似乎是相当普遍的问题，我希望它们是众所周知的，并且在库甚至 SDK 中已经存在解决方案。 我猜第一个是“转置”，因为可以将地图的地图视为矩阵。

Answer 1

    // Transpose a map of maps
Map<Y, Map<X, Z>> transpose(Map<X, Map<Y, Z>> map) {
  Map<Y, Map<X, Z>> transposed = new HashMap<>();
  for (Map.Entry<X, Map<Y, Z>> entry : map.entrySet()) {
    for (Map.Entry<Y, Z> innerEntry : entry.getValue().entrySet()) {
      transposed.computeIfAbsent(innerEntry.getKey(), k -> new HashMap<>()).put(entry.getKey(), innerEntry.getValue());
    }
  }
  return transposed;
}

// Flatten a map of sets
Map<Y, Set> flatten(Map<X, Set> map) {
  Map<Y, Set> flattened = new HashMap<>();
  for (Map.Entry<X, Set> entry : map.entrySet()) {
    flattened.computeIfAbsent(entry.getKey(), k -> new HashSet<>()).addAll(entry.getValue());
  }
  return flattened;
}

我希望这有帮助。

Answer 2

我认为您不会在广泛可用的库中找到这样的转置 OP，但在普通 Groovy 中对它们进行建模相当容易：

def inp1 = [ a:[ X:1, Y:2 ], b:[ Y:3 ] ]
def res1 = inp1.inject( [:].withDefault{ [:] } ){ res, k, v ->
  v.each{ kk, vv -> res[ kk ][ k ] = vv  }
  res
}

assert res1.toString() == '[X:[a:1], Y:[a:2, b:3]]'

// -------------------------

def inp2 = [ a:[ "X", "Y" ] as Set, b:[ "Y", "Z" ] as Set ]
def res2 = inp2.inject( [:].withDefault{ new HashSet() } ){ res, k, v ->
  v.each{ vv -> res[ vv ] << k }
  res
}
assert res2.toString() == '[X:[a], Y:[a, b], Z:[b]]'
assert Set.isAssignableFrom( res2.X.class )

Answer 3

在 Clojure 中，转换看起来像这样：

(defn rotate-map [m]
  (reduce-kv (fn [m k1 m2]
               (reduce-kv (fn [m k2 v] (assoc-in m [k2 k1] v)) m m2))
  {} m))

(defn rotate-set [m]
  (reduce-kv (fn [m k s]
               (reduce (fn [m x]
                         (update m x (fnil conj #{}) k))
                       m s))
             {} m))

测试：

user=> (rotate-map '{a {x 1 y 2} b {y 3}})
{x {a 1}, y {a 2, b 3}}

user=> (rotate-set '{x #{a} y #{a b} z #{b}})
{a #{x y}, b #{y z}}