我想生成一个随机的抽象语法树。
具有指定的大小。
根据Sean Luke在2013年出版的Essentials of Metaheuristics(卢卢出版社第二版),使用该书中的算法,链接为https://cs.gmu.edu/~sean/book/metaheuristics/。
我们随机扩展非叶节点的树的范围,直到非叶节点的数量加上剩余的空位大于或等于所需的大小。然后,我们用叶节点填充剩余的插槽: 例如。
这段文字的翻译如下:
我还尝试使用
除此之外,我还必须以某种方式随机插入新节点/树的位置。
我该如何编写这个算法?
编辑:对正确解决方案的最后润色。
(def terminal-set #{'x 'R})
(def function-arity {'+ 2, '- 2, '* 2, '% 2})
(def function-set (into #{} (keys function-arity)))
(def terminal-vec (into [] terminal-set))
(def function-vec (into [] function-set))
;; protected division
(defn % [^Number x ^Number y]
(if (zero? y)
0
(/ x y)))
具有指定的大小。
(defn treesize [tree] (count (flatten tree)))
根据Sean Luke在2013年出版的Essentials of Metaheuristics(卢卢出版社第二版),使用该书中的算法,链接为https://cs.gmu.edu/~sean/book/metaheuristics/。
我们随机扩展非叶节点的树的范围,直到非叶节点的数量加上剩余的空位大于或等于所需的大小。然后,我们用叶节点填充剩余的插槽: 例如。
(+ (* x (+ x x)) x)
这段文字的翻译如下:
大小为7。
书中的算法使用指针/引用Q
非常方便。在我的情况下,我必须使用某种递归来构建树。问题是我无法在所有使用递归的算法之间保持树的状态size
,这会导致更大的树:
(defn ptc2-tree
"Generate a random tree up to its `max-size`.
Note: `max-size` is the number of nodes, not the same as its depth."
[max-size]
(if (> 2 max-size)
(rand-nth terminal-vec)
(let [fun (rand-nth function-vec)
arity (function-arity fun)]
(cons fun (repeatedly arity #(ptc2-tree (- max-size arity 1)))))))
我还尝试使用
atom
的大小,但无论如何都不能得到我想要的确切树的大小,这取决于实现的大小问题。除此之外,我还必须以某种方式随机插入新节点/树的位置。
我该如何编写这个算法?
编辑:对正确解决方案的最后润色。
(defn sequentiate [v]
(map #(if (seqable? %) (sequentiate %) %) (seq v)))