如何平树？

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，returns 原子列表）：

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

如何平树？

How to flat a tree?

algorithm

tree

scheme

racket