从 Clojure 中的列表创建树

Question

你好，我是Clojure的新手，

我正在尝试解决以下问题1

我解决这个问题的第一步是编写一个函数，该函数接收一个列表（在我的例子中是地名列表）并将其转换为树。

(list 'Karlsruhe 'Stuttgart '100 'Stuttgart 'Ulm '80 'Ulm 'Muenchen '120)

我希望这棵树看起来像这样：2

我希望树看起来像这样的原因是，我计划编写一个函数来接收目标和目的地，在新创建的树中搜索目标，记下所有右侧节点，然后在最后检查哪个最小并返回。

我只是想要一些帮助/指导，谢谢。

米.

Answer 1

你正在尝试做的事情可以在不构造树的情况下完美完成。您的列表中有三胞胎，其中包含源，目标和一些数字。因此，我会在这里制作一个source图[destination number]，以便更好地查找，然后递归遍历它：

(def items (list 'Karlsruhe 'Stuttgart '100 
                 'Stuttgart 'Ulm '80 
                 'Ulm 'Muenchen '120))
(def items-lookup-map (into {} 
                        (map (juxt first rest) 
                             (partition 3 items)))

现在，您的查找映射如下所示：

{Karlsruhe (Stuttgart 100), 
 Stuttgart (Ulm 80), 
 Ulm (Muenchen 120)}

因此，现在您可以轻松编写一个函数来查找从源到目标的路径：

(defn find-path [source dest lookup-map]
  (let [[prev [dest & _]] (split-with
                           #(and (not (nil? %)) (not= % dest))
                           (iterate #(first (lookup-map %))
                                    source))]
    (when dest (concat prev [dest]))))

让我们测试一下：

user> (find-path 'Karlsruhe 'Ulm items-lookup-map)
(Karlsruhe Stuttgart Ulm)
user> (find-path 'Karlsruhe 'Prague items-lookup-map)
nil
user> (find-path 'Moscau 'Ulm items-lookup-map)
nil

现在你可以用它做任何你想做的事情，例如在 path 中查找最小数字：

(defn min-distance [src dest lookup-map]
  (when-let [path (seq (find-path src dest lookup-map))]
    (apply min (map #(second (lookup-map %)) (butlast path)))))
user> (min-distance 'Karlsruhe 'Muenchen items-lookup-map)
80