Clojure中的随机树遍历

Question

如果一棵树编码为一组嵌套列表(例如，(+ 2 (+ 2 1) (+ 1 3 2)))，那么是否有一种已知的算法可以随机遍历树，在单个节点上应用一个参数提供的函数，并且在任何节点上“着陆”的概率相等？注意:在转换单个节点之后，步行就结束了。

我希望该算法的表现如下：

(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 (即，...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)