怎样压平一棵树？

Question

我正在尝试定义一个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)

Answer 1

如果使用(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)))))))