Нахождение максимального количества дочерних узлов в дереве - PullRequest
Новая
       11

Нахождение максимального количества дочерних узлов в дереве

2 голосов
/ 14 января 2011

Во-первых, я должен пояснить, что это необходимо для академического проекта. Я пытаюсь найти максимальное количество дочерних узлов для любого узла в дереве, используя Common Lisp.

Мой текущий код показан ниже - я не на 100% по логике этого, но я чувствую, что он должен работать, однако он не дает мне требуемого результата. 

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

Как пример, работает 

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

должен вернуть 4.

Edit: Результаты трассировки и фактические возвращаемые значения, забыл эти: 

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

У кого-нибудь есть идеи, где я ошибаюсь? Я подозреваю, что это связано со вторым условием, но я не уверен.

Ответы [ 3 ]

4 голосов
/ 15 января 2011

Сначала стандартное форматирование: 

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

Ваша проблема - (setf l y), которая должна дать вам предупреждение о том, что l не определено. Setf не следует использовать для несвязанных переменных. Используйте let для создания лексической области видимости: 

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

Тогда вместо двух вложенных when используйте один и and: 

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

Я считаю dolist более кратким здесь: 

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

Параметр y всегда является длиной параметра list, поэтому этот вызов можно упростить. Вам также не нужно псевдоним 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))
3 голосов
/ 15 января 2011

L не является локальной переменной, поэтому функция вернет последнее назначенное ей значение (т. Е. Ширину последнего поддерева).

Используйте LET для объявления локальной переменной: 

(LET ((l y))
    ...
)
0 голосов
/ 15 января 2011

Не правильный ответ 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)))))))
...