algorithm - Racket 中的随机树

Question

我正在尝试从 Racket 中的列表创建一棵随机树。

这棵树是由一个运营商列表和一个终端列表组成的。

输出将如下所示:

'(* (+ 2 4) 2)

因此可以使用 eval 函数调用列表。

此外，还应指定最大级别。

所以我的猜测是程序如下所示。

(define (make-tree tree level) ... )

我考虑过使用 map 函数并深入扩展每个级别，但我是 lisp-likes 的新手，所以我发现很难找到我需要的算法。

目前每个运算符只接受两个参数(本质上生成的树是二叉树)，但在任何答案中包含如何扩展函数以启用三个或更多参数会很有用。

Answer 1

#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.