정렬 다항식 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))))

이는 다음과 + A * C + A^2 + A * B를, I는 + A * B + C + A * A를^2를 얻을 필요 때문에 * B를 <^2 및 <^2

I 함수 정렬 방법을 사용했지만, 제 출력된다 :

+ A^2 + A * B는 인

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

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

어떤 도움? 감사합니다.

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 더 이상 없습니다.