基於深度的Clojure樹節點

Question

我一直在努力解決遞歸問題，並且我正在用盡想法。基本上，我有一個樹表示，看起來像這樣：

{1 {:root nil} 2 {:root 1} 3 {:root 1} 4 {:root 2} 5 {:root 1} 6 {:root 4}} 

而且我必須建立一個新的樹了最後一個指示父/子關係的水平。有效輸出爲：

{ 1 [3 1] 2 [1] 3 [] 4 [1] 5 [] 6 [] } 

其中每個節點都有一個按關係級別計算的項目數組。所以節點1有3個直接的孩子（2 3 5）和一個孫子（4）。節點2只有一個孩子（4），節點4有一個直接孩子（6），其他所有孩子都是空的（沒有孩子）。

我發現了一些問題like this one實際上幫助，但不是我正在尋找。我也是函數編程的新手，任何幫助都將被讚賞。

Answer 1

我要去假設有在你上面的示例輸出一個錯誤，它確實應該：

{ 1 [3 1 1] 2 [1 1] 3 [] 4 [1] 5 [] 6 [] } 

你的樣品輸出沒有考慮一個事實，即6是一個曾孫1和2的孫子。

我會在這裏詳細介紹一個解決方案。我們將通過編寫針對指定了一棵樹，在樹的頂點，一個功能開始時，計算到樹的頂部從頂點的路徑：

(defn path-to-top [tree v] 
    (if (nil? v) 
     '() 
     (cons v (path-to-top tree (:root (get tree v)))))) 

接下來，讓我們寫一個函數需要從頂點到樹和同事每個頂點的頂部這樣的路徑上這個頂點的距離開始頂點：

(defn steps-indexed-path 
    ([upward-path steps] 
     (if (= upward-path '()) 
      '() 
      (cons [(first upward-path) steps] (steps-indexed-path (rest upward-path) (+ steps 1))))) 
    ([upward-path] 
     (steps-indexed-path upward-path 0))) 

當第一函數返回的頂點列表，這個功能返回一個向量的列表，其中第一個條目是一個頂點，第二個條目是來自第一個條目的步驟數指向頂點的路徑上的第一個頂點。

好吧，當我們在樹中應用此功能，每個頂點，我們將（在某些嵌套形式），每個頂點v和每個後代的wv數據[v <# steps from v to w>]。對於這些數據中的每一個，我們應該在我們的最終解決方案中將與v相關的向量的<# steps from v to w>分量加1。在我們繼續之前的矢量階段，我們只是準水平與計數：

(defn count-descendants [tree] 
    (let [markers (reduce concat '() (map steps-indexed-path (map (partial path-to-top tree) (keys tree))))] 
     (reduce (fn [counter [vertex generation]] (assoc counter vertex (assoc (get counter vertex {}) generation (+ (get (get counter vertex {}) generation 0) 1)))) {} markers))) 

這將產生一個hash-map，它的鍵是v頂點並使得每個頂點對應的v的值是另一個hash-map其中鍵是樹中頂點的不同可能世代的後代，並且值是每一代的後代數。

現在我們所要做的就是把以前的函數的輸出到您指定的格式：

(defn sanitize-descendant-counts [association] 
    (let [max-depth (apply max (keys association))] 
     (map (fn [i] (get association i 0)) (range 1 (+ max-depth 1))))) 

(defn solve-problem [tree] 
    (let [descendant-counts (count-descendants tree)] 
     (apply merge (map (fn [v] (hash-map v (vec (sanitize-descendant-counts (get descendant-counts v))))) (keys descendant-counts))))) 

這是我得到的輸出，當我運行你的例子此代碼：

{1 [3 1 1], 4 [1], 6 [], 3 [], 2 [1 1], 5 []} 

您可以access all the code here，包括你需要在你的榜樣運行什麼。希望有所幫助！

Answer 2

我會盡力勾勒出一個可行的方法，強調遞歸核心，粉飾小的細節。這些細節中有相當多的細節，其中有些細節並不是微不足道的，但它們與遞歸本身無關，只會使答案混亂。從你的樹表示的細節

讓我們抽象。把一棵樹想象成一個節點集合，其中每個節點可以是一個葉子（沒有孩子），否則就是一個分支。假設我們有兩個功能branch?和children。要麼接收一個參數 - 一個節點。 branch?是一個有明顯含義的謂詞，children返回該節點的一個子序列。 （這與tree-seq核心功能預期的合同相同。）我把它留給你，以代碼branch?和children。 （你可能想改變你的樹形表示，以便更容易地編碼這些函數。）

讓我們嘗試創建一個函數levels，給定一個節點將按級別返回一系列數量的子代 - 兒童，孫輩等上。所以，我們會期望你的樹

(levels 1) 
;; => (3 1 1) 
(levels 2) 
;; => (1 1) 

（你有一個錯字，順便節點1有一個盛大的孫子 - 這是6。）

而這裏的核心 - levels：

(defn levels 
    [node] 
    (if (branch? node) 
    (cons (count (children node)) (sum-up-levels (map levels (children node)))) 
    [])) 

這是遞歸的肉。該基本情況是葉 - 當branch?回報false我們知道有沒有孩子，所以水平是空的 - []。否則，我們指望孩子和cons這個數字（即添加到列表）的總結了以下水平。總結意味着按級別總計數字 - 子女總數，孫子女總數等等。在這裏，我們有遞歸 - 我們下降到孩子們，使用map爲每個孩子遞歸調用levels。

的sum-up-levels功能是有點惱人的代碼。我離開這麼多，你填的是我可能只是給我在這裏它的代碼（肯定不是最短的，但我沒有更多的時間來把它擦亮。）

(defn reduce-through 
    [f & colls] 
    (when-let [colls (seq (filter seq colls))] 
    (cons (reduce f (map first colls)) 
      (apply reduce-through f (map rest colls))))) 

(defn sum-up-levels 
    [levels] 
    (apply reduce-through + levels)) 

後定義了levels，很容易以您需要的形式獲得結果。試試吧（一個提示 - 使用tree-seq。）

Answer 3

(defn children-depths [parents] 
    (let [children ; let's first build an inverted index 
     (reduce-kv (fn [children node {parent :root}] 
        (update children parent conj node)) 
      {} parents) 
     depths (fn depths [node] 
       (if-some [nodes (children node)] 
        (into [(count nodes)] 
        ; pads and sums 
        (reduce #(map + (concat %1 (repeat 0)) (depths %2)) 
         nil nodes)) 
        []))] ; no descendants -> empty 
    (into {} (for [node (keys parents)] [node (depths node)])))) 

=> (children-depths {1 {:root nil} 2 {:root 1} 3 {:root 1} 4 {:root 2} 5 {:root 1} 6 {:root 4}}) 
{1 [3 1 1], 2 [1 1], 3 [], 4 [1], 5 [], 6 []} 

一個明顯的改進是爲了避免重複計算兒童的深處。