Сортировка полиномов Common Lisp

Question

Я пытаюсь сортировать список многочленов, записанных в таком формате: (M [коэффициент] [общая степень] [Переменный список]).

пример:

((M 1 1 ((V 1 A))) (M 1 2 ((V 1 A) (V 1 C))) (M 1 2 ((V 2 A))) (M 1 2 ((V 1 A) (V 1 B))))

Это: а + а * с + а^2 + а * Ь, мне нужно, чтобы получить + а * Ь + с + а * а^2, потому что * б < а^2 и < а^2.

Я пытался использовать функцию сортировки, но мой вывод:

((M 1 1 ((V 1 A))) (M 1 2 ((V 2 A))) (M 1 2 ((V 1 A) (V 1 B))) (M 1 2 ((V 1 A) (V 1 C)))) 

что а + а^2 + а * Ь + a * c.

Я использую:

(defun sort-poly (a b) 
    (cond 
    (t (sort-poly-helper (varpowers a) (varpowers b))))) 

(defun sort-poly-helper (a b) 
    (cond 
    ((null a) (not (null b))) 
    ((null b) nil) 
    ((equal (third(first a)) (third(first b))) (sort-poly-helper (rest a) (rest b))) 
    (t (sort (list (third(first a)) (third(first b))) #'string-lessp)))) 

с:

(sort '((M 1 1 ((V 1 A))) (M 1 2 ((V 1 A) (V 1 C))) (M 1 2 ((V 2 A))) (M 1 2 ((V 1 A) (V 1 B)))) #'sort-poly) 

помощь? Thanks

Answer 1

Ваше определение того, что вы хотите сделать, достаточно непрозрачно, что ответить трудно. Но путь для начала - прекратить программирование, так как это 1956 и использовать некоторую абстракцию.

Прежде всего, давайте определим, как сделать переменную и получить на его биты:

(defun make-variable (name &optional (degree 1)) 
    `(v ,name ,degree)) 

(defun variable-name (v) 
    (second v)) 

(defun variable-degree (v) 
    (third v)) 

Теперь давайте определим, как сделать полиномы из списков переменных. Заметим, что полная степень полинома вычислима из степеней всех переменных, поэтому мы это делаем.

(defun make-polynomial (variables &optional (coefficient 1)) 
    ;; The total degree of the polynomial can just be computed from the 
    ;; degrees of its variables 
    `(m ,coefficient ,(reduce #'* variables :key #'variable-degree) 
     ,variables)) 

(defun polynomial-coefficient (p) 
    (second p)) 

(defun polynomical-total-degree (p) 
    (third p)) 

(defun polynomial-variables (p) 
    (fourth p)) 

Теперь данные списки многочленов, мы можем отсортировать их с помощью абстракции мы построили: нам не нужно унижаться вокруг с списком аксессорами (и на самом деле мы могли бы изменить представление полиномов или переменные и ничего не узнает).

Я предполагаю, что то, что вы хотите отсортировать, - это наивысшая степень переменной в полиноме, хотя это не совсем понятно, а не полная степень полинома (что было бы проще). Итак, давайте напишем функцию, чтобы вытащить наивысшую переменную степень:

(defun highest-variable-degree (p) 
    (reduce #'max (mapcar #'variable-degree (polynomial-variables p)))) 

И теперь мы можем сортировать списки полиномов.

CL-USER 23 > (sort (list (make-polynomial (list (make-variable 'a) 
               (make-variable 'b 2))) 
         (make-polynomial (list (make-variable 'c) 
               (make-variable 'd)))) 
        #'< 
        :key #'highest-variable-degree) 
((m 1 1 ((v c 1) (v d 1))) (m 1 2 ((v a 1) (v b 2)))) 

Помните: это не 1956 больше.