clojure - Clojure map transformations (children to fathers in a tree)

Question

Say I have the following map of nodes in a tree and their children:

(def a {0 [], 1 [], 2 [0, 1]})

Corresponding to a tree with node 2 at its root and two leaf-nodes 0 and 1 as node 2's children.

How do I transform it into a map of fathers, or, better yet, adorn it with the fathers. E.g. arrive at the following map of fathers:

{0 2, 1 2, 2 nil} ; each node only has one father at most

Or, better yet, at the following map which combines children and fathers:

{0 [[] 2], 1 [[] 2], 2 [[0,1] nil]}

Answer 1

第一点：

(def a {0 [], 1 [], 2 [0, 1]})

(defn parent-map [m]
  (reduce 
    (fn [x [k v]] 
      (into x (zipmap v (repeat k)))) {} m))

(def parent (parent-map a))   

parent 
=> {1 2, 0 2}
(parent 1)
=> 2 
(parent 2)
=> nil

因此，无需2 nil在父映射中显式设置。

第二位：

(defn parent-child-map [m]
  (let [parent (parent-map m)]
    (reduce 
      (fn [x [k v]] 
        (assoc x k [(m k) (parent k)])) {} m)))

(parent-child-map a)
=> {2 [[0 1] nil], 1 [[] 2], 0 [[] 2]}

更有趣的事情：

(def b {0 [], 1 [], 2 [], 3 [], 4 [0 1 2], 5 [3], 6 [4 5]})

(parent-child-map b)
=>
{6 [[4 5] nil],
 5 [[3] 6],
 4 [[0 1 2] 6],
 3 [[] 5],
 2 [[] 4],
 1 [[] 4],
 0 [[] 4]}

Answer 2

(defn parents [m]
  (let [plist (into {} (for [[k v] m vv v] [vv k]))]
    (into {} (map (fn [[k v]] [k [v (plist k)]]) m))))

(parents a)
=> {0 [[] 2], 1 [[] 2], 2 [[0 1] nil]}