根据符号和指数对多项式排序

Sort Polynomial based on Symbol and Exponent

我正在用 lisp 编写多项式算术,目前正在研究加法。我需要帮助按指数和符号对多项式进行排序。我的多项式表示如下:

((3 ((1 x)(1 y))) (1 ((3 y)))) ; == 3xy + 1y^3

我需要指导的功能被赋予了一个术语

((5 ((3 x))) (3 ((3 y))) (4 ((2 z)))) ((6 ((3 x))) (1 ((3 y))) (9 ((2 z)))))

我想要:

((4 ((2 Z))) (9 ((2 Z))) (5 ((3 X))) (6 ((3 X))) (3 ((3 Y))) (1 ((3 Y))))

返回,所以所有的z^2和z^2都在一起[=13​​=]

您的初始示例显示了具有两个变量的项(例如 3xy),但您稍后的示例没有。该解决方案不会处理多变量项的情况(而且您还没有说在这种情况下您希望如何分组),但它会处理您的示例。

首先,为使用多项式项定义一些抽象概念,因为目前它们相当不方便。这里有三个函数可以更容易地从每个项中提取系数、次数和变量:

(defun polynomial-term-coefficient (term)
  (destructuring-bind (coefficient ((degree variable))) term
    (declare (ignore degree variable))
    coefficient))

(defun polynomial-term-degree (term)
  (destructuring-bind (coefficient ((degree variable))) term
    (declare (ignore coefficient variable))
    degree))

(defun polynomial-term-variable (term)
  (destructuring-bind (coefficient ((degree variable))) term
    (declare (ignore coefficient degree))
    variable))

那么,据我了解你的问题,你实际上是从两个多项式 5x3 + 3y3 + 4z2 和 6x3 + y3 + 9z2。您可以先 将它们添加 在一起,只需附加它们的术语列表即可。然后你可以 sort 谓词 string> (需要 string designators,所以符号是可以的), 关键函数为多项式项变量。也就是说,您使用 key 函数来提取您实际想要排序的值。

(let ((p1 '((5 ((3 x))) (3 ((3 y))) (4 ((2 z)))))
      (p2 '((6 ((3 x))) (1 ((3 y))) (9 ((2 z))))))
  (let ((unsimplified-sum (append p1 p2)))
    (sort (copy-list unsimplified-sum) 'string> :key 'polynomial-term-variable)))
;=> ((4 ((2 Z))) (9 ((2 Z))) (3 ((3 Y))) (1 ((3 Y))) (5 ((3 X))) (6 ((3 X))))

您可能想要搜索 "Horner's method",这是一种在 O(n) 时间内计算多项式值的旧数值方法,n 是项数。它从一开始看起来就接近你想要做的事情,或者至少在表现上相似。