Найти наиболее вложенный список в списке в Common Lisp - PullRequest
Новая
       11

Найти наиболее вложенный список в списке в Common Lisp

6 голосов
/ 13 января 2011

Я новичок в Common Lisp и функциональном программировании, но у меня большой опыт в таких языках, как C, C ++, C #, Java и так далее.У меня проблемы с поиском самого вложенного списка в списке.Мой ввод выглядит примерно так: 

(0 1 (2 3) 4 (5 (6 (7) 8)) 9)

Я хотел бы получить самый вложенный список в этом списке, который в данном случае равен 

(7)

У меня была идея, что я мог быКак-то свести список до тех пор, пока не останется только один подсписок.Чтобы проиллюстрировать, что я имею в виду, вот несколько шагов:

Шаг 1. - ввод: 

(0 1 (2 3) 4 (5 (6 (7) 8)) 9)

Шаг 2. - выравнивание на «первом уровне»: 

(0 1 2 3 4 5 (6 (7) 8) 9)

Шаг 3. - выравнивание на «втором уровне»: 

(0 1 2 3 4 5 6 (7) 8 9)

Теперь остался только один вложенный список, что означает, что это был самый вложенный список.Но я вижу здесь проблему, когда появятся два или более таких списков.Пожалуйста, поделитесь своими мыслями по этому поводу.

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

Ответы [ 3 ]

3 голосов
/ 13 января 2011

Вот мое решение, использующее подход, аналогичный ОП. (В случае нескольких самых глубоких предметов они все возвращаются.)

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

(define (deepest lst)
  (let ((filtered (filter pair? lst)))
    (cond ((null? filtered) lst)
          (else (deepest (concatenate filtered))))))
2 голосов
/ 13 января 2011

Вот мое (не очень чистое) решение в CL: 

(defun deepest-list (lst)
  (let ((max-depth 0) ret)
    (labels ((inner-deepest-lst (lst depth)
           (cond
         ((null lst) depth)
         ((listp (car lst))
          (let ((local-max (max
                    (inner-deepest-lst (first lst) (1+ depth))
                    (inner-deepest-lst (rest lst)  (1+ depth)))))
            (and (> local-max max-depth) (setf ret (first lst) max-depth local-max))
            local-max))
         (t (inner-deepest-lst (rest lst) depth)))))
      (inner-deepest-lst lst 1))
    ret))

редактирование:

Подумав, это немного более чистое решение: 

(defun deepest-list (lst)
  (labels ((dl (lst depth)
         (cond
           ((atom lst) (cons 0 lst))
           ((every #'atom lst) (cons depth lst))
           (t (funcall (lambda (x y) (if (> (car x) (car y)) x y))
               (dl (car lst) (1+ depth))
               (dl (cdr lst) depth))))))
    (rest (dl lst 0))))
2 голосов
/ 13 января 2011

Ваш подход итеративного сглаживания списка, вероятно, должен работать нормально, хотя это не самый эффективный или (субъективно) элегантный способ сделать это.

Если таких списков больше одного, правильный выводзависит от спецификации - должны ли вы вернуть все из них, или только первое, или выдать ошибку?

На вашем месте я бы хотел придумать рекурсивную функцию для решенияпроблема.Каждый уровень рекурсии будет в основном обрабатывать элементы данного уровня вложенных списков.Подумайте, что должен делать каждый рекурсивный вызов - это очень просто, если один раз он щелкнет!

...