基于深度的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 []} 

一个明显的改进是为了避免重复计算儿童的深处。