首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >最长子列表的LISP长度

问最长子列表的LISP长度
EN

Stack Overflow用户
提问于 2019-01-13 02:51:54
回答 1查看 425关注 0票数 1

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

我尝试过这样做:

代码语言:javascript
复制
(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)))
    )   
)

对于上面的示例,它返回4,但问题是它只分析子列表的第一级。如果我尝试为列表(1 (2 (3 (4 5 a a a a)) (6 7) 8) 9)解析它,它也会返回4,尽管由于列表(4 5 a a a a),它应该是6,但它仍然只接受列表(2 (3 (4 5 a a a a)) (6 7) 8)。

提前谢谢你。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2019-01-13 03:35:38

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

函数的第一个草图如下所示,基于LOOP宏(您仍然需要一些工作才能将其转换为完全递归的解决方案):

代码语言:javascript
复制
(defun longest-length (tree)
  (loop for subtree in tree maximize (longest-length subtree)))

正如上面所解释的,您将问题划分为子问题,通过查找每个子树的最长长度来递归地解决它们,并通过返回每个局部最大值的最大值来组合它们。

但是上面的代码遗漏了一些东西。首先,您需要考虑应该计算树本身的长度:

代码语言:javascript
复制
(defun longest-length (tree)
  (max (length tree)
       (loop for subtree in tree maximize (longest-length subtree))))

此外,当代码到达非cons单元格的项时,它也会失败。您现在必须为树不是cons-cell的基本情况添加代码。特别是,nil被视为一个空列表,而不是一个符号:

代码语言:javascript
复制
(defun longest-length (tree)
  (typecase tree
    (cons (max (length tree)
               (loop
                 for subtree in tree
                 maximize (longest-length subtree))))
    (null 0)
    (t 1)))

下面是一个测试:

代码语言:javascript
复制
CL-USER> (longest-length '(1 (2 (3 (4 5 a a a a)) (6 7) 8) 9))
6

还可以考虑使用reduce,与apply不同,它对列表(call-argument-limit)中的元素数量没有限制:

代码语言:javascript
复制
(reduce #'max (mapcar ... tree) :initial-value (length tree))
票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/54162838

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档