查找從樹根到葉子的所有路徑在方案

所以，對於這種樹：

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))))

這比我原來的更整潔。

來源

2010-06-10 grifaton

我在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))

來源

2010-06-11 00:07:19 Svante

考慮到它處理具有單個節點的樹的方式，這是相當整潔的 - 並且可能更正確：（paths'a）=> （（a）），而（g'a）=>（a）。 CL的地圖可以或多或少地等於我的地圖2以上？你知道內置的Scheme功能嗎？ – grifaton 2010-06-11 07:15:58

我對Scheme的瞭解不多，但我會猜想像mapcan這樣的東西可用。不過，也許它被認爲很容易實現。你的'map2'原則上看起來是相同的，但是它的尾部調用錯誤，所以當列表太長時它會打擊棧。也許你應該使用累加器/反向習慣用法。 – Svante 2010-06-11 08:33:20

等同於'mapcan'的方案是來自SRFI-1的'append-map'。 – 2010-06-11 12:14:56

我認爲你可以將示例樹定義爲（root左右）每一個列表。因此，您的示例樹將是：（D（B（A（）（C（）（F（）G）））E）（）），並且更容易遍歷

來源

2010-06-10 23:35:23 Ismael

我想你誤解了我的圖 - A是樹的根。另外（這個問題可能並不明確），一個節點可以有兩個以上的分支，所以我認爲你的方法不會奏效。 – grifaton 2010-06-10 23:40:54

我剛剛意識到我誤解了你的圖表。我會說，如果g函數可以工作，你應該使用:-) – Ismael 2010-06-10 23:42:47

您需要樹搜索算法。廣度優先或深度優先遍歷都可以工作，在這種情況下，由於您需要抓取整個樹，所以沒有區別。每當你到達葉子時，只需將當前路徑存儲在結果中。

來源

2010-06-10 23:59:59 Greg

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))))

來源

2010-06-11 08:51:07

查找從樹根到葉子的所有路徑在方案

回答

相關問題