最长子列表的 LISP 长度

Question

我想生成最长子列表的长度。例如，对于列表 (1 (2 (3 (4 5)) (6 7) 8) 9) ，结果将为 4，因为子列表 (2 (3 (4 5)) (6 7) 8) 的长度为 4。

我试过这样做：

(defun len(l)
    (cond
         ((null l) 0)
         ((atom l) 1)
         (t (+ (len(cdr l)) 1))
    )
)
(defun lun(l)
    (cond
        ((atom l) 1)
        (t(apply #'max (mapcar #' len l)))
    )   
)

对于上面的例子，它returns 4，但问题是它只分析了子列表的第一层。如果我尝试为列表 (1 (2 (3 (4 5 a a a a)) (6 7) 8) 9) 解析它，它也会 returns 4，即使它应该是 6 因为列表 (4 5 a a a a)，它仍然只需要列表 (2 (3 (4 5 a a a a)) (6 7) 8) .

提前致谢。

Answer 1

您的输入是列表列表（等）的列表，也称为树。您想要计算构成树的列表之一的最长长度。粗略地说，您需要遍历子树，计算它们各自的最长长度，并将这些长度组合成一个新的最大长度。

函数的第一个草图如下，基于 LOOP 宏（您还需要做一些工作才能将其转换为完全递归的解决方案）：

(defun longest-length (tree)
  (loop for subtree in tree maximize (longest-length subtree)))

就像上面解释的那样，你把你的问题分成子问题，递归地解决它们通过寻找对于每个子树，它们的最长长度，并通过返回每个局部最大值的最大值。

但是上面遗漏了几件事。首先，您需要考虑到应该计算树的长度本身：

(defun longest-length (tree)
  (max (length tree)
       (loop for subtree in tree maximize (longest-length subtree))))

此外，代码在到达非cons-cells 项目时失败。您现在必须为树不是cons-cells 的基本情况添加代码。特别是， nil 被视为空列表而不是符号：

(defun longest-length (tree)
  (typecase tree
    (cons (max (length tree)
               (loop
                 for subtree in tree
                 maximize (longest-length subtree))))
    (null 0)
    (t 1)))

这是一个测试：

CL-USER> (longest-length '(1 (2 (3 (4 5 a a a a)) (6 7) 8) 9))
6

也考虑使用 reduce，它不像 apply 对列表中的元素数量没有限制 (call-argument-limit)：

(reduce #'max (mapcar ... tree) :initial-value (length tree))

最长子列表的 LISP 长度

LISP length of the longest sublist

lisp

clisp

list

common-lisp