Длина LISP самого длинного подсписка - PullRequest
Новая
       43

Длина LISP самого длинного подсписка

0 голосов
/ 12 января 2019

Я хочу создать длину самого длинного подсписка. Например, для списка (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)))
    )   
)

Для приведенного выше примера возвращается 4, но проблема в том, что он анализирует только первый уровень подсписка. Если я пытаюсь разрешить его для списка (1 (2 (3 (4 5 a a a a)) (6 7) 8) 9), он также возвращает 4, хотя он должен быть равен 6 из-за списка (4 5 a a a a), он по-прежнему принимает только список (2 (3 (4 5 a a a a)) (6 7) 8).

Заранее спасибо.

1 Ответ

0 голосов
/ 12 января 2019

Ваш ввод - это список списков списков (и т. Д.), Также известный как деревья. Вы хотите вычислить самую длинную длину одного из списков, составляющих дерево. Грубо говоря, вам нужно перебрать поддеревья, вычислить их наибольшую длину и объединить их в новую максимальную длину.

Первый эскиз функции выглядит следующим образом на основе макроса 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-ячейками. В частности, ноль рассматривается как пустые списки, а не как символ: 

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