ツリー内の子ノードの最大数を調べる

Question

まず、これは学術プロジェクトに必要であることを明確にする必要があります。私はCommon Lispを使用して、ツリー内の任意のノードの子ノードの最大数を見つけようとしています。

私の現在のコードは以下に示されています - 私はそのロジックの100％ではありませんが、動作するはずですが、必要な結果が得られていません。返す必要があり

(max-breadth '(a ((b (c d)) e) (f g (h i) j))) 

を実行している例として

(defun breadth (list y) 
    (setf l y) 
     (mapcar #'(lambda (element) 
       (when (listp element) 
     (when (> (breadth element (length element)) l) 
      (setf l (breadth element (length element))) 
      ))) list) 

l) 

(defun max-breadth(list) 
    (breadth list (length list)) 
) 

、4

編集： トレース結果と実際の戻り値は、忘れてしまったこれら：

CG-USER(13): (max-breadth '(a ((b (c d)) e) (f g (h i) j))) 
0[6]: (BREADTH (A ((B (C D)) E) (F G (H I) J)) 3) 
    1[6]: (BREADTH ((B (C D)) E) 2) 
    2[6]: (BREADTH (B (C D)) 2) 
     3[6]: (BREADTH (C D) 2) 
     3[6]: returned 2 
    2[6]: returned 2 
    1[6]: returned 2 
    1[6]: (BREADTH (F G (H I) J) 4) 
    2[6]: (BREADTH (H I) 2) 
    2[6]: returned 2 
    1[6]: returned 2 
0[6]: returned 2 
2 

は誰もが持っています私が間違っているどんなアイデア？私はそれが第2の条件に関係していると思うが、私はよくわからない。

Answer 1

まず、標準の書式設定を：

(defun breadth (list y) 
    (setf l y) 
    (mapcar #'(lambda (element) 
       (when (listp element) 
       (when (> (breadth element (length element)) l) 
        (setf l (breadth element (length element)))))) 
      list) 
    l) 

(defun max-breadth (list) 
    (breadth list (length list))) 

あなたの問題はあなたに未定義であることの警告についてlを与える必要があります(setf l y)、です。 Setfは、バインドされていない変数には使用しないでください。私はここにdolistをより簡潔見つける

   (when (and (listp element) 
         (> (breadth element (length element)) 1)) 
       (setf l (breadth element (length element)))) 

：単一のものとandを使用し、代わりに2つの入れ子whenで、その後

(defun breadth (list y) 
    (let ((l y)) 
    (mapcar #'(lambda (element) 
       (when (listp element) 
        (when (> (breadth element (length element)) l) 
        (setf l (breadth element (length element)))))) 
      list) 
    l)) 

：レキシカルスコープを作るためにletを使用し

(dolist (element list) 
    (when (and (listp element) 
       (> (breadth element (length element)) l)) 
     (setf l (breadth element (length element))))) 

パラメータyは常にパラメータlistの長さなので、この呼び出しはsim plified。また、別名yする必要はありません。

(defun breadth (list &aux (y (length list))) 
    (dolist (element list) 
    (when (and (listp element) 
       (> (breadth element) y)) 
     (setf y (breadth element)))) 
    y) 

あなたはletを通じて、二重再帰呼び出しをなくすことができ、私たちはここにmaxを使用することができます。

(defun breadth (list &aux (y (length list))) 
    (dolist (element list) 
    (when (listp element) 
     (setf y (max y (breadth element))))) 
    y) 

ます。また、このためにreduceを使用することができます。

を

(defun breadth (l) 
    (if (listp l) 
     (reduce #'max l 
       :key #'breadth 
       :initial-value (length l)) 
     0)) 

Answer 2

正解6ではありませんか？あなたの例のeとjも技術的に子ノードなので、それはあなたの問題を定義している方法です場合は、以下のソリューションがあなたを取得する必要があります。

(defun max-breadth (lst) 
    (cond 
    ((atom lst) 0) 
    ((every #'atom lst) (length lst)) 
    (t (+ (max-breadth (car lst)) (max-breadth (cdr lst)))))) 

バージョン2：

(defun max-breadth (lst) 
    (cond 
    ((atom lst) 0) 
    ((every #'atom lst) (length lst)) 
    (t (+ 
     (max-breadth (car lst)) 
     (max-breadth (remove-if-not #'consp (cdr lst))))))) 

Answer 3

をLはローカル変数ではないので、関数は最後の値を返します。それに割り当てられた（すなわち、最後のサブツリーの幅）。

使用LETは、ローカル変数を宣言します

(LET ((l y)) 
    ... 
)