sorting - 排序多项式 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 + a * b，我需要得到a + a * b + c + a * a ^ 2，因为a * b < a ^ 2且a < a ^ 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 + a ^ 2 + a * 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 年。