2

ツリー内のノードとその子の次のマップがあるとします。

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

ルートにノード2があり、ノード2の子として2つのリーフノード0と1があるツリーに対応します。

どうすればそれを父親の地図に変換できますか、さらに良いことに、父親で飾ることができます。たとえば、次の父親の地図に到着します。

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

または、さらに良いことに、子供と父親を組み合わせた次のマップで：

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

2 に答える 2

4

最初のビット：

(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したがって、親マップに明示的に含める必要はありません。

2番目のビット：

(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]}
于 2013-02-22T18:24:54.803 に答える
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]}
于 2013-02-22T18:35:43.937 に答える