排序多项式Common Lisp [英] Sort polynomials Common Lisp

问题描述

我正在尝试对以这种格式编写的多项式列表进行排序: (M [系数] [总度数[变量列表]).

I'm trying to sort a list of polynomials written in this format: (M [coefficient] [total degree] [Variable List]).

示例:

((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 ^ 2.

This is: a + a * c + a ^ 2 + a * b, I need to get a + a * b + c + a * a ^ 2, because a * b < a ^ 2 and a < a ^ 2.

我尝试使用函数sort，但是我的输出是:

I tried to use the function sort, but my output is:

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

that is 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)

有帮助吗? 谢谢

推荐答案

您对要执行的操作的定义非常不透明，因此很难提供答案.但是开始的方法是停止像1956年这样的编程，并使用某种抽象.

Your definition of what you want to do is sufficiently opaque that an answer is hard to provide. But the way to start is to stop programming like it is 1956 and use some abstraction.

首先，让我们定义如何创建变量并获得其结果:

First of all, let's define how to make a variable and get at its bits:

(defun make-variable (name &optional (degree 1))
  `(v ,name ,degree))

(defun variable-name (v)
  (second v))

(defun variable-degree (v)
  (third v))

现在让我们定义如何从变量列表中生成多项式.请注意，多项式的总次数可以从所有变量的次数中得出，因此我们可以做到这一点.

Now let's define how to make polynomials from lists of variables. Note that the total degree of the polynomial is computable from the degrees of all the variables, so we do that.

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

现在，在给定多项式列表的情况下，我们可以使用构建的抽象对它们进行排序:我们不需要在列表访问器中四处徘徊(事实上，我们可以更改多项式或变量的表示形式，一无所知).

Now, given lists of polynomials, we can sort them using the abstractions we've built: we don't need to grovel around with list accessors (and indeed we could change the representation of polynomials or variables and nothing would ever know).

我猜想要排序的是多项式中变量的最高阶，尽管尚不清楚，而不是多项式的总阶(这会更容易).因此，让我们编写一个函数来提取最高可变度:

I am guessing that what you want to sort on is the highest degree of a variable in a polynomial although it is not really clear, and not the total degree of the polynomial (which would be easier). So let's write a function to pull out the highest variable degree:

(defun highest-variable-degree (p)
  (reduce #'max (mapcar #'variable-degree (polynomial-variables p))))

现在我们可以对多项式列表进行排序了.

And now we can sort lists of polynomials.

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年.

这篇关于排序多项式Common Lisp的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！