按普通 lisp 中的两个属性排序
Sorting by two attributes in common lisp
我需要帮助按普通 lisp 中的两个属性进行排序。
假设我有一个列表：
(1 x)(2 y)(1 x)(2 x)(3 y)(2 y) 我正在尝试按字符串和整数进行排序。
所以结果将是 (1 x)(1 x)(2 x)(2 y)(2 y)(3 y).
目前我可以按变量或数字排序，但不能同时按两者排序。如果我输入 (2 x)(1 x)(1 y)(2 x)(1 y) 我得到的是 (1 Y)(1 Y)(2 X)(1 X)(2 X) 而不是 (1 Y)(1 Y)(1 X)(2 X)(2 X)
我使用的代码是：
(defun get-number (term)
(destructuring-bind (number variable) term
(declare (ignore variable))
number))
(defun get-variable (term)
(destructuring-bind (number variable) term
(declare (ignore number))
variable))
(defun varsort (p1)
(sort (copy-list p1) 'string> :key 'get-variable))
我的问题是如何按整个术语排序，以便 (1 X) 而不仅仅是 1 或 X。
两个选项：
stable-sort根据get-numbervarsort的结果
定义要在 sort 中使用的自定义比较函数：
;; choose a better name
(compare-by-string-and-number (x y)
(let ((vx (get-variable x))
(vy (get-variable y)))
(or (string> vx vy)
(and (string= vx vy)
(> (get-number x)
(get-number y))))))
是编写通用比较函数的好方法。并且由于您正在操作元组，因此您可以更具体一点并编写以下内容：
(defun tuple-compare (comparison-functions)
(lambda (left right)
(loop for fn in comparison-functions
for x in left
for y in right
thereis (funcall fn x y)
until (funcall fn y x))))
例如：
(sort (copy-seq #((1 2) (2 3) (1 3) (2 1)))
(tuple-compare (list #'< #'<)))
=> #((1 2) (1 3) (2 1) (2 3))
您可以利用所涉及列表的不同长度：例如，您只能通过提供一个比较函数来根据第一个参数进行排序。如果你想用相同的比较函数比较所有可用的元素对，你也可以创建一个循环列表。
(stable-sort (copy-seq #((1 2 4) (1 3 6) (1 2 6) (2 3 4) (1 3) (2 1)))
(tuple-compare (list* #'> (circular-list #'<))))
=> #((2 1) (2 3 4) (1 2 4) (1 2 6) (1 3 6) (1 3))
(循环列表在alexandria中可用)
真正的词典排序将确保较短的列表在较长的列表之前排序，前提是它们共享一个共同的前缀：例如，它会在 (1 3 6) 之前排序 (1 3)。可能的修改如下：
(defun tuple-compare (comparison-functions &optional lexicographic)
(lambda (left right)
(loop for fn in comparison-functions
for (x . xr) on left
for (y . yr) on right
do (cond
((funcall fn x y) (return t))
((funcall fn y x) (return nil))
((and lexicographic yr (null xr)) (return t))))))
您可以通过组合谓词来做到这一点。如果你有一个可以比较变量的谓词和一个可以比较系数的谓词，那么你可以很容易地创建一个新的谓词来检查一个，如果第一个谓词提供了一个明确的答案，则返回一个明确的答案，或者推迟到第二个谓词，如果没有。这也将可重复用于其他应用程序：
(defun and-then (original-predicate next-predicate)
"Returns a new predicate constructed from ORIGINAL-PREDICATE and
NEXT-PREDICATE. The new predicate compares two elements, x and y, by
checking first with ORIGINAL-PREDICATE. If x is less than y under
ORIGINAL-PREDICATE, then the new predicate returns true. If y is less
than x under ORIGINAL-PREDICATE, then the new predicate returns false.
Otherwise, the new predicate compares x and y using NEXT-PREDICATE."
(lambda (x y)
(cond
((funcall original-predicate x y) t)
((funcall original-predicate y x) nil)
(t (funcall next-predicate x y)))))
然后很容易调用 (and-then 'variable< 'coefficient<)。首先，一些访问器和谓词：
(defun term-coefficient (term)
(first term))
(defun coefficient< (term1 term2)
(< (term-coefficient term1)
(term-coefficient term2)))
(defun term-variable (term)
(second term))
(defun variable< (term1 term2)
(string< (term-variable term1)
(term-variable term2)))
现在测试：
(defparameter *sample*
'((1 x)(2 y)(1 x)(2 x)(3 y)(2 y)))
CL-USER> (sort (copy-list *sample*) 'coefficient<)
((1 X) (1 X) (2 Y) (2 X) (2 Y) (3 Y))
CL-USER> (sort (copy-list *sample*) 'variable<)
((1 X) (1 X) (2 X) (2 Y) (3 Y) (2 Y))
CL-USER> (sort (copy-list *sample*) (and-then 'variable< 'coefficient<))
((1 X) (1 X) (2 X) (2 Y) (2 Y) (3 Y))
您可以定义一个 compare-by 函数来创建其中一些谓词函数，这可以使它们的定义更简单一些，或者可能完全删除。
(defun compare-by (predicate key)
"Returns a function that uses PREDICATE to compare values extracted
by KEY from the objects to compare."
(lambda (x y)
(funcall predicate
(funcall key x)
(funcall key y))))
您可以简单地定义谓词：
(defun coefficient< (term1 term2)
(funcall (compare-by '< 'term-coefficient) term1 term2))
(defun variable< (term1 term2)
(funcall (compare-by 'string< 'term-variable) term1 term2))
或完全摆脱它们：
(defun varsort (p1)
(sort (copy-list p1)
(and-then (compare-by '< 'term-coefficient)
(compare-by 'string< 'term-variable))))
我需要帮助按普通 lisp 中的两个属性进行排序。
假设我有一个列表：
(1 x)(2 y)(1 x)(2 x)(3 y)(2 y) 我正在尝试按字符串和整数进行排序。
所以结果将是 (1 x)(1 x)(2 x)(2 y)(2 y)(3 y).
目前我可以按变量或数字排序，但不能同时按两者排序。如果我输入 (2 x)(1 x)(1 y)(2 x)(1 y) 我得到的是 (1 Y)(1 Y)(2 X)(1 X)(2 X) 而不是 (1 Y)(1 Y)(1 X)(2 X)(2 X)
我使用的代码是：
(defun get-number (term)
(destructuring-bind (number variable) term
(declare (ignore variable))
number))
(defun get-variable (term)
(destructuring-bind (number variable) term
(declare (ignore number))
variable))
(defun varsort (p1)
(sort (copy-list p1) 'string> :key 'get-variable))
我的问题是如何按整个术语排序，以便 (1 X) 而不仅仅是 1 或 X。
两个选项：
stable-sort根据get-number得到定义要在
sort中使用的自定义比较函数：;; choose a better name (compare-by-string-and-number (x y) (let ((vx (get-variable x)) (vy (get-variable y))) (or (string> vx vy) (and (string= vx vy) (> (get-number x) (get-number y))))))
varsort的结果
(defun tuple-compare (comparison-functions)
(lambda (left right)
(loop for fn in comparison-functions
for x in left
for y in right
thereis (funcall fn x y)
until (funcall fn y x))))
例如：
(sort (copy-seq #((1 2) (2 3) (1 3) (2 1)))
(tuple-compare (list #'< #'<)))
=> #((1 2) (1 3) (2 1) (2 3))
您可以利用所涉及列表的不同长度：例如，您只能通过提供一个比较函数来根据第一个参数进行排序。如果你想用相同的比较函数比较所有可用的元素对，你也可以创建一个循环列表。
(stable-sort (copy-seq #((1 2 4) (1 3 6) (1 2 6) (2 3 4) (1 3) (2 1)))
(tuple-compare (list* #'> (circular-list #'<))))
=> #((2 1) (2 3 4) (1 2 4) (1 2 6) (1 3 6) (1 3))
(循环列表在alexandria中可用)
真正的词典排序将确保较短的列表在较长的列表之前排序，前提是它们共享一个共同的前缀：例如，它会在 (1 3 6) 之前排序 (1 3)。可能的修改如下：
(defun tuple-compare (comparison-functions &optional lexicographic)
(lambda (left right)
(loop for fn in comparison-functions
for (x . xr) on left
for (y . yr) on right
do (cond
((funcall fn x y) (return t))
((funcall fn y x) (return nil))
((and lexicographic yr (null xr)) (return t))))))
您可以通过组合谓词来做到这一点。如果你有一个可以比较变量的谓词和一个可以比较系数的谓词，那么你可以很容易地创建一个新的谓词来检查一个，如果第一个谓词提供了一个明确的答案，则返回一个明确的答案，或者推迟到第二个谓词，如果没有。这也将可重复用于其他应用程序：
(defun and-then (original-predicate next-predicate)
"Returns a new predicate constructed from ORIGINAL-PREDICATE and
NEXT-PREDICATE. The new predicate compares two elements, x and y, by
checking first with ORIGINAL-PREDICATE. If x is less than y under
ORIGINAL-PREDICATE, then the new predicate returns true. If y is less
than x under ORIGINAL-PREDICATE, then the new predicate returns false.
Otherwise, the new predicate compares x and y using NEXT-PREDICATE."
(lambda (x y)
(cond
((funcall original-predicate x y) t)
((funcall original-predicate y x) nil)
(t (funcall next-predicate x y)))))
然后很容易调用 (and-then 'variable< 'coefficient<)。首先，一些访问器和谓词：
(defun term-coefficient (term)
(first term))
(defun coefficient< (term1 term2)
(< (term-coefficient term1)
(term-coefficient term2)))
(defun term-variable (term)
(second term))
(defun variable< (term1 term2)
(string< (term-variable term1)
(term-variable term2)))
现在测试：
(defparameter *sample*
'((1 x)(2 y)(1 x)(2 x)(3 y)(2 y)))
CL-USER> (sort (copy-list *sample*) 'coefficient<)
((1 X) (1 X) (2 Y) (2 X) (2 Y) (3 Y))
CL-USER> (sort (copy-list *sample*) 'variable<)
((1 X) (1 X) (2 X) (2 Y) (3 Y) (2 Y))
CL-USER> (sort (copy-list *sample*) (and-then 'variable< 'coefficient<))
((1 X) (1 X) (2 X) (2 Y) (2 Y) (3 Y))
您可以定义一个 compare-by 函数来创建其中一些谓词函数，这可以使它们的定义更简单一些，或者可能完全删除。
(defun compare-by (predicate key)
"Returns a function that uses PREDICATE to compare values extracted
by KEY from the objects to compare."
(lambda (x y)
(funcall predicate
(funcall key x)
(funcall key y))))
您可以简单地定义谓词：
(defun coefficient< (term1 term2)
(funcall (compare-by '< 'term-coefficient) term1 term2))
(defun variable< (term1 term2)
(funcall (compare-by 'string< 'term-variable) term1 term2))
或完全摆脱它们：
(defun varsort (p1)
(sort (copy-list p1)
(and-then (compare-by '< 'term-coefficient)
(compare-by 'string< 'term-variable))))