球拍中的随机树
Random Tree in Racket
我正在尝试从 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.
我正在尝试从 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.