list - 创建所有可能的树(Creating all possible trees)

Question

Before I describe the function I want to write, I will provide some data definitions.

(在描述我要编写的函数之前，我将提供一些数据定义。)

;; An Op (Operator) is an (anyof '+ '- '* '/).

;; A BET (Binary Expression Tree) is either a:
;; * Nat
;; * (list Op BET BET)

So I want to implement the function make-all-bets, which consumes a list of permutations of a list of numbers and a list of $n$-tuples of operators and produces a list of all possible BET's using the provided permutations and $n$-tuples, considering all possible tree structures.

(所以我想实现make-all-bets函数，该函数使用数字列表和$ n $ -tuples运算符列表的排列列表，并使用提供的排列和$ n生成所有可能的BET列表$元组，考虑所有可能的树结构。)

Note: the function requires that the length of each list in the first list the function consumes is 1 greater than the length of each list in the second list the function consumes.

(注意：该函数要求该函数使用的第一个列表中每个列表的长度比该函数使用的第二个列表中每个列表的长度大1。)

The contract below should make things easier to understand.

(以下合同应使事情更容易理解。)

;; (make-all-bets nln nlp) produces a list of all possible BET's
;;   using nln nlp.
;; make-all-bets: (listof (listof Num)) (listof (listof Op)) -> (listof BET)
;; requires: (length nln) - (length nlp) = 1

Also, the following check-expects give an idea of what the function should produce:

(此外，以下检查期望也可以使函数产生什么效果：)

(check-expect
 (make-all-bets
  '((8 6 4 2))
  '((/ + -)))
 '((/ 8 (+ 6 (- 4 2)))
   (/ 8 (+ (- 6 4) 2))
   (/ (+ 8 6) (- 4 2))
   (/ (+ 8 (- 6 4)) 2)
   (/ (+ (- 8 6) 4) 2)))
(check-expect
 (make-all-bets
  '((8 6 2))
  '((/ +)))
 '((/ 8 (+ 6 2))
   (/ (+ 8 6) 2)))

A hint I was given was that I need to consider all the ways to partition $n-1$ nodes b/w the left and right subtrees of a node and then, through recursion, build the left and right subtrees.

(我得到的提示是，我需要考虑使用$ n-1 $个节点在节点的左和右子树之间进行分区的所有方法，然后通过递归构建左和右子树。)

For a given n, there are $C_n$ possible trees, where $C_n$ is the $n$th Catalan number, calculated by $\prod_{k=2}^n \dfrac{n+k}{n}$.

(对于给定的n，有$ C_n $个可能的树，其中$ C_n $是第n个加泰罗尼亚语数字，由$ \ prod_ {k = 2} ^ n \ dfrac {n + k} {n} $计算得出。)

Also, nested calls to map are apparently helpful.

(而且，嵌套调用map显然很有帮助。)

It also might be helpful to take two intermediate steps:

(采取两个中间步骤可能也会有所帮助：)

1. Implement a function (make-left-right-pairs node-cnt) that produces a list of number-pairs indicating the size of the left and right subtrees for a given overall-node-count on a tree.

   (实现一个函数（make-left-right-pairs node-cnt），该函数生成一个数字对列表，该数字对列表指示树上给定的总节点数的左右子树的大小。)

   For instance, the following check-expects should be satisfied

   (例如，应满足以下检查要求)

(check-expect (make-left-right-pairs 3) '((2 0) (1 1) (0 2)))
(check-expect (make-left-right-pairs 4) '((4 0) (3 1) (2 2) (1 3) (0 4)))

2. Implement (make-tree-structure node-cnt) which produces a list of trees w/o putting in the values for internal nodes (operators) and leaves (numbers).

   (实现（make-tree-structure node-cnt），它生成没有内部节点（运算符）和叶子（数字）值的树列表。)

   Each node value represents the number of nodes.

   (每个节点值代表节点数。)

   For instance, consider the following check-expect:

   (例如，考虑以下检查期望：)

(check-expect (make-tree-structure 3)
              '((3 empty (2 empty (1 empty empty)))
                (3 empty (2 (1 empty empty) empty))
                (3 (1 empty empty) (1 empty empty))
                (3 (2 empty (1 empty empty)) empty)
                (3 (2 (1 empty empty) empty) empty)))

So I can implement the two helper functions, but I don't know how to combine the helper functions to create the function (make-all-bets nln nlp).

(因此，我可以实现这两个辅助函数，但是我不知道如何组合辅助函数来创建该函数（make-all-bets nln nlp）。)

I can see how the function's output resembles the output of (make-tree-structure), but I don't know how to implement that into code.

(我可以看到函数的输出如何类似于（make-tree-structure）的输出，但是我不知道如何将其实现为代码。)

Any help would be appreciated (no code for the helper functions is necessary since I already know how to implement them).

(任何帮助将不胜感激（因为我已经知道如何实现它们，所以不需要用于辅助函数的代码）。)

  ask by bob translate from so

Answer 1

Looks like once you get the result of your second helper — make-tree-structure — you can simply map all the nodes to operators and the leaves to numbers within each tree in the list.

(看起来，一旦获得第二个助手的结果-make make-tree-structure ，就可以简单地将所有节点映射到运算符，将叶子映射到列表中每棵树中的数字。)

#lang htdp/isl+

(require 2htdp/abstraction)

(define tree-structure
  '((3 empty (2 empty (1 empty empty)))
    (3 empty (2 (1 empty empty) empty))
    (3 (1 empty empty) (1 empty empty))
    (3 (2 empty (1 empty empty)) empty)
    (3 (2 (1 empty empty) empty) empty)))

(check-expect (map-all-trees tree-structure '(/ + -) '(8 6 4 2))
              '((/ 8 (+ 6 (- 4 2)))
                (/ 8 (+ (- 6 4) 2))
                (/ (+ 8 6) (- 4 2))
                (/ (+ 8 (- 6 4)) 2)
                (/ (+ (- 8 6) 4) 2)))

; [List-of Tree] [List-of Symbol] [Lis-of Number] -> [List-of Tree]
; convert a tree structure to a BET by mapping all nodes and leaves
(define (map-all-trees tree-structure operations numbers)
  (local
    (; Tree [List-of Symbol] [Lis-of Number] -> Tree
     ; map nodes and trees for the tree
     (define (map-tree tree o n)
       (map-leaves (map-nodes tree o) n)))
    (map (λ (t) (map-tree t operations numbers)) tree-structure)))

; Tree [List-of Symbol] -> Tree
; maps all nodes in tree with new-nodes from left to right
(define (map-nodes tree new-nodes)
  (local
    (; Tree -> Boolean
     ; does t have a numerical node?
     (define (num-as-node? t)
       (and (not (symbol? t))
            (or (number? (first t))
                (num-as-node? (second t))
                (num-as-node? (third t)))))
     ; Tree Symbol -> Tree
     ; replaces left-most node in t with s
     (define (replace-node t s)
       (match t
         ['empty t]
         [(list n l r)
          (cond [(number? n) (list s l r)]
                [else (if (num-as-node? l)
                          (list n (replace-node l s) r)
                          (list n l (replace-node r s)))])]))
     ; Tree [List-of Symbol] -> Tree
     ; replaces nodes till all elems in l are placed in t
     (define (replace-all-nodes t l)
       (match l
         ['() t]
         [(cons f r) (replace-all-nodes (replace-node t f) r)])))
    (replace-all-nodes tree new-nodes)))

; Tree [List-of Number] -> Tree
; maps all leaves in tree with new-leaves from left to right
(define (map-leaves tree new-leaves)
  (local
    (; Tree [List-of Number] -> Tree
     ; replace all leafs in t with l from left to right
     (define (replace-all-leaf t l)
       (match l
         ['() t]
         [(cons f r) (replace-all-leaf (replace-leaf t f) r)]))
     ; Tree -> Boolean
     ; does tree have 'empty as a leaf in it?
     (define (empty-in-tree? t)
       (match t
         [(? symbol?) (symbol=? t 'empty)]
         [(? number?) #false]
         [(list n l r)
          (or (and (symbol? l) (symbol=? 'empty l))
              (and (symbol? r) (symbol=? 'empty r))
              (empty-in-tree? l)
              (empty-in-tree? r))]))
     ; Tree Number -> Tree
     ; replace the left-most 'empty leaf in t with n
     (define (replace-leaf t node)
       (match t
         ['empty node]
         [(list n l r)
          (if (empty-in-tree? l)
              (list n (replace-leaf l node) r)
              (list n l (replace-leaf r node)))])))
    (replace-all-leaf tree new-leaves)))