algorithm - 如何平整一棵树？

我试图定义一个topological-sort函数来生成一个图的拓扑排序的所有可能顺序：

(define (topological-sort graph)
  (if (null? graph)
      `()
      (map (lambda (x)
             (cons x
                   (topological-sort (reduce x graph))))
           (no-in-edge graph))))

只获取树（多层列表）

'((a
   (b
    (c
     (e
      (d (f))
      (f (d))))
    (e
     (c
      (d (f))
      (f (d)))
     (d
      (c
       (f)))))
   (e
    (b
     (c
      (d (f))
      (f (d)))
     (d
      (c (f))))
    (d
     (b
      (c
       (f)))))))

怎么能把这棵树排列成一个列表呢？

a, b, c, e, f, d
a, e, b, c, f, d
a, b, e, c, f, d
a, e, d, b, c, f
a, e, b, d, c, f
a, b, e, d, c, f
a, b, c, e, d, f
a, e, b, c, d, f
a, b, e, c, d, f

我试过几个旅行功能，但都失败了。
总计划：

(define (no-in-edge graph)
  (filter (lambda (x)
            (and (element x
                               (vertex graph))
                 (not (element x
                                    (out-vertex graph)))))
          (vertex graph)))

(define (reduce x graph)
  (if (null? graph)
      `()
      (if (eq? x (caar graph))
          (reduce x
                  (cdr graph))
          (cons (car graph)
                (reduce x (cdr graph))))))

(define (element x list)
  (if (null? list)
      #f
      (if (eq? x (car list))
          #t
          (element x (cdr list)))))

(define (vertex graph)
  (map car graph))

(define (out-vertex graph)
  (remove-duplicates (apply append
                            (map cdr graph))))

(define (top-level graph)
  (apply append (topological-sort graph)))

(define (topological-sort graph)
  (if (null? graph)
      `()
      (map (lambda (x)
             (cons x
                   (topological-sort (reduce x graph))))
           (no-in-edge graph))))

(define test-graph `((a b c e)
                     (b c)
                     (c f)
                     (e d f)
                     (d)
                     (f)))

(topological-sort test-graph)

最佳答案

如果使用(list-paths (car tree) '())调用，此过程将列出所有路径：

(define list-paths
  (lambda (tree path)
    (if (null? (cdr tree))
        (reverse (cons (car tree) path))
        (map
         (lambda (subtree)
           (list-paths subtree (cons (car tree) path)))
          (cdr tree)))))

如果您想平展结果，可以使用自定义过程（而不是通常的返回原子列表的flatten）来完成此操作：

(define flatten
  (lambda (ll)
    (cond ((null? ll) ll)
          ((symbol? (car ll))
           (list ll))
          (else
           (append
            (flatten (car ll))
            (flatten (cdr ll)))))))

关于algorithm - 如何平整一棵树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38342362/