多項式を並べ替える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 + A * C + A^2 + * bの、私は+ A * B + C + *のA^2を取得する必要があり、 * bの<^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)))) 

は+ A^2 + * bであること+ 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、それ以上ではありません。