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

Question

我正在用 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 都在一起。

Answer 1

您的初始示例显示了具有两个变量的项(例如 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))

然后，据我了解你的问题，你实际上是从两个多项式 5x³ + 3y³ + 4z² 和 6x ³ + y³ + 9z²。您可以先将它们加在一起，只需附加它们的术语列表即可。然后你可以排序谓词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))))