我试图从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/

10-09 13:26