Найти все пути от корня до листьев дерева на схеме - PullRequest
Новая
       6

Найти все пути от корня до листьев дерева на схеме

3 голосов
/ 11 июня 2010

Учитывая дерево, я хочу найти пути от корня до каждого листа.

Итак, для этого дерева: 

    D
   /
  B
 / \ 
A   E
 \
  C-F-G

имеет следующие пути от корня (A) до листьев (D, E, G): 

(A B D), (A B E), (A C F G)

Если я представляю дерево выше как (A (B D E) (C (F G))), то функция g делает свое дело: 

(define (paths tree)
  (cond ((empty? tree)
         '())
        ((pair? tree)
         (map (lambda (path)
                (if (pair? path)
                    (cons (car tree) path)
                    (cons (car tree) (list path))))
              (map2 paths (cdr tree))))
        (else
         (list tree))))

(define (map2 fn lst)
  (if (empty? lst)
      '()
      (append (fn (car lst))
              (map2 fn (cdr lst)))))

Но это выглядит неправильно. Некоторое время мне не приходилось так думать, но я чувствую, что должен быть более аккуратный способ сделать это. Буду признателен за любые идеи для лучшего решения (на любом языке).

РЕДАКТИРОВАТЬ - Отображение решения Сванте в Схеме дает: 

(define (paths tree)
  (if (pair? tree)
      (append-map (lambda (node)
              (map (lambda (path)
                     (cons (car tree) path))
                   (paths node)))
            (cdr tree))
      (list (list tree))))

что намного аккуратнее моего оригинала.

Ответы [ 4 ]

3 голосов
/ 11 июня 2010

Я более свободно говорю на Common Lisp. 

(defun paths (tree)
  (if (atom tree)
      (list (list tree))
      (mapcan (lambda (node)
                (mapcar (lambda (path)
                          (cons (car tree) path))
                        (paths node)))
              (cdr tree))))

CL-USER> (paths '(A (B D E) (C (F G))))
((A B D) (A B E) (A C F G))
2 голосов
/ 11 июня 2010

R5RS перевод ответа Сванте: 

(define (accumulate op init seq)
  (define (iter ans rest)
    (if (null? rest)
        ans
        (iter (op ans (car rest))
              (cdr rest))))
  (iter init seq))

(define (flatten seq)
  (accumulate append '() seq))

(define (flatmap op seq)
  (flatten (map op seq)))

(define (atom? x)
  (not (pair? x)))

(define (paths tree)
  (if (atom? tree)
      (list (list tree))
      (flatmap (lambda (node)
                 (map (lambda (path)
                        (cons (car tree) path))
                      (paths node)))
               (cdr tree))))
0 голосов
/ 11 июня 2010

Вы хотите алгоритм поиска по дереву. Обход в ширину или в глубину может сработать, и в этом случае не имеет значения, как вам нужно обходить все дерево. Всякий раз, когда вы добираетесь до листа, просто сохраняйте текущий путь в ваших результатах.

0 голосов
/ 11 июня 2010

Я думаю, вы можете определить дерево примеров как (корень слева направо), каждый из которых является списком. Таким образом, ваш пример дерева будет: (D (B (A () (C () (F () G))) E) ()), и это легче пройти

...