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

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

Студворк — интернет-сервис помощи студентам

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

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

Lisp
1
2
3
4
5
6
7
(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
1
2
3
4
> (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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
;; Сортировка выбором
 
(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
1
2
3
4
5
6
7
8
9
10
11
(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
1
2
3
4
5
6
7
8
9
10
11
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
;; Для списков и векторов. Сортировка с флагом.
(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)

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

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

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