Выстроить атомы в многоуровневом списке в один уровень по возрастанию

@syxomlinka · Регистрация: 28.12.2014

Написать функцию in-one-level(x), которая выстраивает атомы в многоуровневом списке x в один уровень по возрастанию

У меня есть наброски, которые преобразует многоуровневый в одноуровневый, но вот с сортировкой по возрастанию у меня проблемка...

Lisp

(defun in-one-level (l) 
(cond 
    ((null l) nil)
    ((atom l) (list l))
    (t (append 
            (in-one-level (car l)) 
            (in-one-level (cdr l)) ))) )

Помогите, пожалуйста!

@castorsky · 10.01.2015, 17:05

syxomlinka, классики учат разбивать задачи на более мелкие задачи. В данном случае задачу можно разделить на две:
1. Функция, которая делает список "плоским", т.е. без уровней. Ищем flatten
2. Функция, которая сортирует список. Ищем sort (я где-то на форуме писал сортировку слиянием merge-sort или как-то так).

@_sg · 10.01.2015, 17:53

как вариант:

Lisp

> (flatten '(7 ((3 5 (((4) 6 1) 0)) 2)))
(7 3 5 4 6 1 0 2)
> (sort-flatten '(7 ((3 5 (((4) 6 1) 0)) 2)))
(0 1 2 3 4 5 6 7)

@Catstail · 10.01.2015, 18:25

Сообщение от syxomlinka

выстраивает атомы

- наверное, все-таки - числа, а не атомы.

@syxomlinka · 10.01.2015, 18:28 **[ТС]**

ну тогда уж символы

Потому что в списке могут быть не только цифры)

@Catstail · 10.01.2015, 18:33

HomeLisp:

Lisp

;; Сортировка выбором
 
(defun vsort (lst)
  (cond ((null lst) nil)
        (t (let ((m (apply 'min lst)))
                 (cons m (vsort (removef m lst)))))))
 
==> vsort
 
(vsort '(1 2 3 1 2 3 4 -6))
 
==> (-6 1 1 2 2 3 3 4)
 
;; Уплощение списка (порядок нарушается, но потом все равно сортировка...)
 
(defun flat (lst)
  (let ((res nil))
    (dolist (i lst res)
      (if (atom i) (push i res) (setf res (append (flat i) res))))))
 
==> flat
 
(flat '((1 2) 11 (((5 6 ((7 9)) 3)))))
 
==> (3 9 7 6 5 11 2 1)
 
;; Решение
 
(defun task (lst)
  (vsort (flat lst)))
 
==> task
 
(task '((1 2) 11 (((5 6 ((7 9)) 3)))))
 
==> (1 2 3 5 6 7 9 11)

Добавлено через 35 секунд
syxomlinka, чем цифра отличается от числа?

@_sg · 10.01.2015, 18:41

Lisp

(defun flatten (w &optional acc) 
  (cond ((null w) acc)
        ((atom w) (cons w acc))
        ((flatten (car w) (flatten (cdr w) acc)))))
 
(defun sort-flatten (w) (sort (flat w) #'<))
 
> (flatten '(7 ((3 5 (((4) 6 1) 0)) 2)))
(7 3 5 4 6 1 0 2)
> (sort-flatten '(7 ((3 5 (((4) 6 1) 0)) 2)))
(0 1 2 3 4 5 6 7)

Добавлено через 17 секунд

Lisp

(defun flatten (w)
  (loop for a in w 
        if (and a (atom a)) collect a
        else nconc (flat a)))
 
(defun sort-flatten (w) (sort (flat w) #'<))
 
> (flatten '(7 ((3 5 (((4) 6 1) 0)) 2)))
(7 3 5 4 6 1 0 2)
> (sort-flatten '(7 ((3 5 (((4) 6 1) 0)) 2)))
(0 1 2 3 4 5 6 7)

@Lambdik · 10.01.2015, 19:19

Lisp

;; Для списков и векторов. Сортировка с флагом.
(defun bubble (seq &optional (p #'<))
  (do ((len (1- (length seq)) (1- len))
       (flag T))
      ((eq flag nil))
    (setq flag nil)
    (do ((i 0 (1+ i)) x y)
        ((= i len))
      (setq x (elt seq i)
            y (elt seq (1+ i)))
        (when (not (funcall p x y))
          (rotatef (elt seq i) (elt seq (1+ i)))
          (setq flag T))))
    seq)
 
(bubble #(2 3 1 9 5 6 8 7 1 4))
; #(1 1 2 3 4 5 6 7 8 9)
(bubble '(2 3 1 9 5 6 8 7 1 4) #'>)
;  (9 8 7 6 5 4 3 2 1 1)

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	10.01.2015, 17:05	2
	syxomlinka, классики учат разбивать задачи на более мелкие задачи. В данном случае задачу можно разделить на две: 1. Функция, которая делает список "плоским", т.е. без уровней. Ищем flatten 2. Функция, которая сортирует список. Ищем sort (я где-то на форуме писал сортировку слиянием merge-sort или как-то так). 1

@Catstail Модератор 33875 / 18902 / 3981 Регистрация: 12.02.2012 Сообщений: 31,692 Записей в блоге: 13
	10.01.2015, 18:25	4
	Сообщение от syxomlinka выстраивает атомы - наверное, все-таки - числа, а не атомы. 1

@syxomlinka 1 / 1 / 0 Регистрация: 28.12.2014 Сообщений: 13
	10.01.2015, 18:28 [ТС]	5
	ну тогда уж символы Потому что в списке могут быть не только цифры) 0

Опции темы