Сортировка элементов в списке [дубликат]
Примечание автора: Это неэффективно. Но весело, потому что монады потрясающие. Это не подходит для производственного кода Python.
>>> sum(l, [])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Это просто суммирует элементы итерабельности, переданные в первом аргументе, обрабатывая второй аргумент как начальное значение суммы (если не указано, 0 вместо этого этот случай даст вам ошибку).
Поскольку вы суммируете вложенные списки, вы фактически получаете [1,3]+[2,4] в результате sum([[1,3],[2,4]],[]), который равен [1,3,2,4].
Обратите внимание, что работает только в списках списков. Для списков списков списков вам понадобится другое решение.
5 ответов
Я больше привык к Scheme, но вот решение, которое работает в Lisp:
(defun f (lst)
(labels
((loop (lst atoms lists)
(cond
((null lst)
(append (reverse atoms) (reverse lists)))
((atom (car lst))
(loop (cdr lst) (cons (car lst) atoms) lists))
(T
(loop (cdr lst) atoms (cons (car lst) lists))))))
(loop lst '() '())))
(f '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6))
В основном вы перебираете список, и каждый элемент либо добавляется к списку атомов, либо списку списков.
EDIT
Вариант remove-if, конечно, короче:
(let ((l '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6)))
(append
(remove-if-not #'atom l)
(remove-if #'atom l)))
-
1– user1392317 14 May 2012 в 10:20
-
2– user1392317 15 May 2012 в 19:42
-
3– uselpa 15 May 2012 в 19:47
-
4– user1392317 15 May 2012 в 19:52
-
5– uselpa 15 May 2012 в 19:56
Вы можете сделать этот рекурсивный путь:
(defun f (lst)
(cond
((null lst) nil)
((atom (car lst))
(append (list (car lst)) (f (cdr lst))))
(T
(append (f (cdr lst)) (list (f (car lst))))
)
)
)
(step (f '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6)))
Выход:
step 1 --> (F '(5 -1 (2 6 1) (8 7 -3) ...))
step 1 ==> value: (5 -1 -6 (0 (9 4)) (8 7 -3) (2 6 1))
В Common Lisp существует несколько возможных подходов:
- использовать REMOVE-IF для удаления нежелательных элементов. (В качестве альтернативы используйте REMOVE-IF-NOT, чтобы сохранить нужные элементы.) Вам понадобятся два списка. Добавляйте их.
- используйте DOLIST и перебирайте список, собирайте элементы в два списка и добавьте их.
- напишите рекурсивную процедуру, в которой вам нужно сохранить два списка результатов.
- также следует использовать SORT со специальным предикатом сортировки.
Пример:
> (sort '(1 (2 6 1) 4 (8 7 -3) 4 1 (0 (9 4)) -6 10 1)
(lambda (a b)
(atom a)))
(1 10 -6 1 4 4 1 (2 6 1) (8 7 -3) (0 (9 4)))
В качестве стабильной версии:
(stable-sort '(1 (2 6 1) 4 (8 7 -3) 4 1 (0 (9 4)) -6 10 1)
(lambda (a b)
(and (atom a)
(not (atom b)))))
(1 4 4 1 -6 10 1 (2 6 1) (8 7 -3) (0 (9 4)))
-
1– user1392317 14 May 2012 в 10:19
-
2– Will Ness 14 May 2012 в 15:43
На всякий случай вам захочется больше заниматься, и вы обнаружите, что приведенных здесь примеров недостаточно: P
(defun sort-atoms-first-recursive (x &optional y)
(cond
((null x) y)
((consp (car x))
(sort-atoms-first-recursive (cdr x) (cons (car x) y)))
(t (cons (car x) (sort-atoms-first-recursive (cdr x) y)))))
(defun sort-atoms-first-loop (x)
(do ((a x (cdr a))
(b) (c) (d) (e))
(nil)
(if (consp (car a))
(if b (setf (cdr b) a b (cdr b)) (setf b a d a))
(if c (setf (cdr c) a c (cdr c)) (setf c a e a)))
(when (null (cdr a))
(cond
((null d) (return e))
((null c) (return d))
(t (setf (cdr b) nil (cdr c) d) (return e))))))
(sort-atoms-first-recursive '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6))
(sort-atoms-first-loop '(5 -1 (2 6 1) (8 7 -3) (0 (9 4)) -6))
Второй - разрушительный (но не создает никаких новых conses).
Вот итеративный код, создающий его вывод сверху вниз (комментарий в синтаксисе Haskell):
;atomsFirst xs = separate xs id id where
; separate [] f g = f (g [])
; separate (x:xs) f g
; | atom x = separate xs (f.(x:)) g
; | True = separate xs f (g.(x:))
(defmacro app (l v)
`(progn (rplacd ,l (list ,v)) (setq ,l (cdr ,l))))
(defun atoms-first (xs)
(let* ((f (list nil)) (g (list nil)) (p f) (q g))
(dolist (x xs)
(if (atom x) (app p x) (app q x)))
(rplacd p (cdr g))
(cdr f)))
Два промежуточных списка, которые строятся сверху вниз поддерживаются как открытые списки (т. е. с явным указателем окончания), по существу следуя парадигме разностных списков.