Максимальный возрастающий подсписок - Lisp

Узнай цену своей работы

Формулировка задачи:

Ребят, помогите пожалуйста! Задание:Построить максимальный растущий подсписок для заданного числового списка. Например, для списка (2 3 1 -1 2 5 10 0 8) есть шесть максимальных растущих подсписков: (2 3 5 10), (1 2 5 10), (-1 2 5 10), (-1 2 5 8 ), (2 3 5 8) и (1 2 5 8). Подсписок на 4 позиции должен быть меньше списке.

Решение задачи: «Максимальный возрастающий подсписок»

textual
Листинг программы
;; Генерация очередной битовой шкалы
 
(defun next-scale (sc)
  (cond ((null sc) nil)
        ((= 0 (car sc)) (cons 1 (cdr sc)))
        (t (cons 0 (next-scale (cdr sc))))))
 
;; Получение подсписка по шкале
 
(defun get-list (lst scale)
  (remove nil (mapcar (lambda (x y) (if (zerop x) nil y)) scale lst)))
 
;; Выделение списков максимальной длины
 
(defun max-lst (lst)
  (let ((m (apply 'max (mapcar 'length lst))))
    (remove-if (lambda (x) (< (length x) m)) lst)))
 
;; Собственно решение:
 
(defun task (lst &optional (sc (cons 1 (replicate 0 (- (length lst) 1)))) (res nil))
  (cond ((zerop (apply '+ sc)) (max-lst res))
        (t (let ((a (get-list lst sc)))
             (if (apply '< a) (task lst (next-scale sc) (cons a res))
                              (task lst (next-scale sc) res))))))
 
==> TASK
 
(task '(2 3 1 -1 2 5 10 0 8))
 
==> ((-1 2 5 8) (1 2 5 8) (2 3 5 8) (-1 2 5 10) (1 2 5 10) (2 3 5 10))

Оцени полезность:

12   голосов , оценка 4.083 из 5
Похожие ответы