我试图从racket的列表中创建一个随机树。
树由运算符列表和终端列表组成。
输出如下:
'(* (+ 2 4) 2)
所以这个列表可以用eval函数调用。
此外,应该指定一个最大级别。
所以我猜程序如下。
(define (make-tree tree level) ... )
我考虑过使用
map
函数并在深度上扩展每个级别,但我对lisp likes还不熟悉,所以我发现很难找到所需的算法。目前,每个运算符只接受两个参数(基本上生成的树是二叉树),但是在任何答案中都应该包括如何扩展函数以启用三个或更多参数。
最佳答案
#lang racket
(define (random-from-list xs)
(list-ref xs (random (length xs))))
;; A TERMINAL is one if terminal1, terminal2, ...
(define TERMINALS '(0 1 2 3 4 5 6 7 8 9))
(define (random-terminal)
(random-from-list TERMINALS))
;; An OPERATOR is one of '+ '-, '* '/ .
(define OPERATORS '(+ - * /))
(define (random-operator)
(random-from-list OPERATORS))
;; A TREE is either
;; i) a terminal
;; or ii) (list operator terminal1 terminal2 ... terminalN)
(define (random-tree . ignore)
(match (random 5)
[0 (random-list-tree)] ; probability 1/5 = 20%
[_ (random-terminal)]))
(define (random-list-tree)
(define N (+ 2 (random (+ 3 1)))) ; at least two operands, at most 2+3
(cons (random-operator) (build-list N random-tree)))
要生成特定深度的树:
1. generate a tree T
2. find the depth D of T
3. if the depth D is of the desired depth return T
4. otherwise go to 1.
关于algorithm - Racket 中的随机树,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32784083/