1

フォームの隣接リストからツリーを構築する関数を作成しようとしています{node [children]}。

(def adjacency
  {nil [:a]
   :a [:b :c]
   :b [:d :e]
   :c [:f]})

その結果、

{nil {:a {:b {:d nil
              :e nil}
          :c {:f nil}}}}

しかし、私はそれを機能させることができませんでした。再帰は私の弱点であり、私が見つけたほとんどの再帰の例は、ツリーではなくリストに対する再帰のみを扱っていました。

編集済み:投稿時に編集者と元のソースがなかったため、元のデータセットと結果の入れ子が意図せず深すぎました。申し訳ありません。

4

2 に答える 2

2

のすべてのサブマップにはエントリが1つだけありadjacencyます。これは必要ですか？そして結果の同じ問題tree。

私はそれがより明確になることを願っています：

(def adjacency {:a [:b :c]
                :b [:d :e]
                :c [:f]})

したがって、解決策は次のとおりです。

(defn tree [m root]
  (letfn [(tree* [l]
            (if (contains? m l)
              {l (into {} (map tree* (m l)))}
              [l nil]))]
    (tree* root)))

テスト：

(tree adjacency :a)
=> {:a {:b {:d nil
            :e nil}
        :c {:f nil}}}

更新します。ネストされたマップとして結果ツリーが必要ない場合

(defn tree [m root]
  (letfn [(tree* [l]
            (if (contains? m l)
              (list l (map tree* (m l)))
              (list l nil)))]
    (tree* root)))

(tree adjacency :a)
=> (:a ((:b ((:d nil)
             (:e nil)))
        (:c ((:f nil)))))
于 2013-01-20T07:15:24.333 に答える
2

私は通常clojure.walk、木を扱うときに使用することを好みます。adjacencyルート ノードがベクトルの最初にあると想定しています。

(use 'clojure.walk)

(def adjacency
  [{nil [:a]}
   {:a [:b :c]}
   {:b [:d :e]}
   {:c [:f]}])

(prewalk
 (fn [x]
   (if (vector? x)
     (let [[k v] x lookup (into {} adjacency)]
       [k (into {} (map (fn [kk] [kk (lookup kk)]) v))])
     x))
 (first adjacency))

結果：{nil {:a {:b {:d {}, :e {}}, :c {:f {}}}}}

注: 空の子は{}ではなくとして表されnilます。子要素はベクトルではなくマップであるため、マップを使用するとこのツリーを簡単にナビゲートできます。

于 2013-01-20T09:57:45.100 に答える