Clojure中的随机树遍历

Question

给定一棵树编码为一组嵌套列表(例如，(+ 2 (+ 2 1) (+ 1 3 2)))， Clojure中是否有一种已知的算法可以随机遍历树，在单个节点上应用参数化提供的函数，在任何节点上"着陆"的概率相等?注意:该遍历在单个节点转换后终止。

我期望算法的行为如下:

(def tree '(1 (1 (1 1 1) 1) 1))
(stochastic-tree-f-app inc tree) => (1 (1 (1 2 1) 1) 1)
(stochastic-tree-f-app inc tree) => (1 (1 (1 1 2) 1) 1)
(stochastic-tree-f-app inc tree) => (2 (1 (1 1 1) 1) 1)
(stochastic-tree-f-app inc tree) => (1 (1 (1 1 1) 1) 2)
(stochastic-tree-f-app dec tree) => (1 (1 (1 1 1) 0) 1)

Answer 1

使用clojure.zip:

(require '[clojure.zip :as z])
(defn stochastic-tree-f-app [f tree]
  (let [zp    (z/zipper list? seq (fn [_ c] c) tree)
        nodes (->> (iterate z/next zp)
                   (take-while (complement z/end?))
                   (filter (comp integer? z/node))
                   (into []))]
    (-> (rand-nth nodes)
        (z/edit f)
        z/root)))

Answer 2

您可以简单地使用clojure。如果最后一个要求可以取消(即. ...在转换单个节点后，Walk终止)。或者用拉链遍历节点，并以编辑结束。使用clojure . walk:

(use 'clojure.walk)
(def tree '(1 (1 (1 1 1) 1) 1))
(defn stochastic-tree-f-app [f tree]
  (let [cnt (atom 0)
        _   (postwalk #(if (integer? %) (swap! cnt inc)) tree)
        idx (rand-int @cnt)]
    (reset! cnt 0)
    (postwalk #(if (and (integer? %) (= idx (swap! cnt inc)))
                (f %)
                %)
              tree)))
user> (stochastic-tree-f-app inc tree)
(2 (1 (1 1 1) 1) 1)
user> (stochastic-tree-f-app inc tree)
(1 (1 (1 1 1) 2) 1)