代码之家 › 专栏 › 技术社区 › EviL GaMer

为什么这种排序算法会做它应该做的事情?[Lisp]

common-lisp lisp sorting

EviL GaMer · 技术社区 · 11 年前

我正在做旧的考试,为自己的考试做准备,教授也很好地为我们提供了解决方法,现在我想知道为什么一个函数会做它应该做的事情。

(defun sortulists (L)
  (mapcar (lambda (uliste)
            (sort uliste (lambda (x1 x2)
                           (or (symbolp x2)
                               (and (numberp x1) (numberp x2)
                                    (< x1 x2))))))
          L))

它应该有一个列表 L 未排序的子列表可能包含数字和原子,首先对数字进行排序,然后将符号放在末尾。

这样叫的时候 (sortulists '((A 9 b h 2) (1 m n 9 8) (5 a 7))) 它会返回 ((2 9 H B A) (1 8 9 N M) (5 7 A)) .

有什么帮助吗?

编辑:固定缩进

3 回复 | 直到 11 年前

Pascal 11 年前

的谓词 sort 函数说明序列排序后,什么测试必须为真。未定义排序的方式。

如果你与 and 和 or 由于它们在这里被使用,我建议你阅读这一章条件属于 Common Lisp: A Gentle Introduction to Symbolic Computation 。它显示了如何交换 cond ,嵌套 if s和组合 和 和 或 ,并提供练习(及其解决方案)。

简而言之,要么右边必须有一个符号,要么如果两者都是数字,则必须按大小排序。

Rainer Joswig mmmmmm 11 年前

(or
    ; if x2 is a symbol, then x1 is smaller, whatever x1 is
    (symbolp x2)

    ; if both are numbers, then return t if x1 is smaller than x2
    (and (numberp x1) (numberp x2)
         (< x1 x2)))

所以数字是排序的,在前面。符号在末尾,但未排序。

Sylwester 11 年前

因此,要说明显而易见的:

(defun sortulists (L)
  (mapcar (lambda (uliste)
            (sort uliste (lambda (x1 x2)
                           (or (symbolp x2)
                               (and (numberp x1) (numberp x2)
                                    (< x1 x2))))))
          L))

mapcar 只需列出将匿名函数应用于每个元素的列表。所以只关注一个元素 '(A 9 b h 2) 您可以执行以下操作:

;; same as the anonymous lambda, but named so we can test it a little
(defun my< (x1 x2)
  (or (symbolp x2)
      (and (numberp x1) (numberp x2)
           (< x1 x2))))

(sort '(A  9  b  h  2) #'my<) ; ==> (2 9 B H A)

(my< 2 'a)                    ; ==> T 
(my< 2 3)                     ; ==> T
(my< 3 3)                     ; ==> NIL
(my< 'a 2)                    ; ==> NIL
(my< 'a 'b)                   ; ==> T
(my< 'b 'a)                   ; ==> T

正在查看 my< x1 小于 x2 如果 x2个 是一个符号。 x1个 如果它们都是数字和 x1个 算术小于 x2个 。其他的一切 x1个 等于或大于 x2个 .

如果你在参数列表中混合了一些符号,你可能会发现你得到的符号的顺序与原始列表不同。原因是两个符号比较后会变成 t 两种方式都如此 'a 小于 'b 和 “b” 小于 '一个 。我们保持结果中符号顺序的版本如下所示:

(stable-sort '(A  9  b  h  2)
      (lambda (x1 x2)
        (and (numberp x1) 
             (or (not (numberp x2))
                 (< x1 x2)))))
; ==> (2 9 A B H)

注意,我使用了 stable-sort 用作 sort 不能保证稳定。稳定意味着相等的对象保持与源相同的顺序。