Сортировка по двум атрибутам в общем lisp

Question

Мне нужна помощь, сортировка по двум атрибутам в общем 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.

Answer 1

Два варианта:

• stable-sort результат varsort по 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)))))) 
  

Joshua's answer хороший способ написать общий comp функции. И так как вы манипулируете кортежи, вы можете быть немного более конкретными и написать следующее:

(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)

truyly лексикографическая сортировка обеспечит более короткие списки будут отсортированы прежде, чем более длинные, при условии, что они имеют общий префикс, например, это было бы сортировать (1 3) перед тем (1 3 6). Возможна следующая модификация:

(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)))))) 

Answer 2

Вы можете сделать это, составив предикаты. Если у вас есть предикат, который может сравнивать переменные и предикат, который может сравнивать коэффициенты, то вы можете легко создать новый предикат, который проверяет один, возвращая определенный ответ, если первый предикат дает определенный ответ или откладывается на второй предикат , в случае, если это не так. Это будет повторно использоваться для других применений, тоже:

(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))))) 

Тогда это достаточно легко сделать вызов (и-то «переменной <» коэффициент <).Во-первых, некоторые аксессоров и предикаты:

(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)) 

Вы могли бы определить сравнения-на функции для создания некоторых из этих функций предиката, которые могли бы сделать их определения немного проще или, возможно, полностью удалить.

(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))))