Я хотел бы создать случайное абстрактное синтаксическое дерево
(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)))
следуя алгоритму из книги Шона Люка, 2013 г., Essentials of Metaheuristics, Lulu, второе издание, доступно по адресу 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
для размера, но все еще не мог получить точный размер дерева, который мне нужен, он был либо слишком маленьким, либо слишком большим, в зависимости от реализации.
Помимо этого, мне также нужно каким-то образом рандомизировать место, куда я вставляю новый узел/дерево.
Как написать этот алгоритм?
EDIT: последний штрих к правильному решению:
(defn sequentiate [v]
(map #(if (seqable? %) (sequentiate %) %) (seq v)))