1

私は木を手に入れました：

(A . ((C . ((D . nil)(E . nil)))
      (B . ((F . nil)(G . nil)))))

このツリーを次のように変換したいと思います。

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

私はすでにこの関数を実装しました：

(defun tree->paths (tree &optional buff)
  (labels ((recurse (follow-ups extended-list)
             (if follow-ups
                 (append (list (tree->paths (car follow-ups) extended-list))
                         (recurse (cdr follow-ups) extended-list))
               nil)))
    (rstyu:aif (cdr tree)
               (recurse it (append buff (list (car tree))))
               (append buff (list (car tree))))))

しかし、それを適用すると、次のようになります。

(tree->paths '(A . ((C . ((D . nil) (E . nil)))
                    (B . ((F . nil) (G . nil))))))
=>
(((A C D) (A C E)) ((A B F) (A B G)))

再帰内で何らかの追加/マージが欠落している必要がありますが、表示されていません。

4

3 に答える 3

1

を削除する必要がありlistます(append (list (tree->paths

はパスのtree->pathsリストを返します。そうrecurseです。したがって、それらはlist呼び出しでラップせずに追加される場合があります。

于 2013-01-20T20:09:55.977 に答える
0

ここでは、線形に動作するように書き直そうとしました (元の関数がスタック スペースを使い果たすため)。ただし、そうしているうちに、一般的にあなたの元のアイデアと見なすことができる何かを発見しました。

(defun tree-to-paths (tree)
  (loop with node = tree
       with trackback = nil
       with result = nil
       with head = nil
       with head-trackback = nil
       while (or node trackback) do
       (cond
         ((null node)
          (setf node (car trackback)
                trackback (cdr trackback)
                result (cons head result)
                head (car head-trackback)
                head-trackback (cdr head-trackback)))
         ((consp (car node))
          (setf trackback (cons (cdr node) trackback)
                head-trackback (cons head head-trackback)
                head (copy-list head)
                node (car node)))
         (t (setf head (cons (car node) head)
                  node (cdr node))))
       finally (return (nreverse (mapcar #'nreverse result)))))

サンプルデータでは、受け取りたい結果は直感的に正しいように見えますが、次のようにさらに多くのパスがあるかのように考えることができます。

A -> C -> NIL- データを見ると、この結果は冗長に見えますが、一般的には、これらの結果も取得したい場合があります。一般的に、すべての結果を除外するのは難しいでしょう。

于 2013-01-21T14:53:11.070 に答える
0

質問で試したように、最初からやり直して、ルートからリーフではなくリーフからルートに移動するという逆のアプローチを選択しました。

(defun tree->paths2 (tree)
  (labels ((recurse (follow-ups)
         (if follow-ups
         (append (tree->paths2 (car follow-ups))
             (recurse (cdr follow-ups)))
         nil)))
    (rstyu:aif (cdr tree)
           (mapcar #'(lambda(arg)
               (cons (car tree) arg))
               (recurse it))
           (list tree))))

(tree->paths2 '(A . ((C . ((D . nil) (E . nil)))
                     (B . ((F . nil) (G . nil))))))
=>
((A C D) (A C E) (A B F) (A B G))

しかし、私の最初のアプローチを修正する方法があれば、そのような修正を答えとして受け入れたいと思います。

于 2013-01-20T18:55:54.587 に答える