7.1 多項式の連想リスト表現

多項式は展開された形、因数分解された形、部分的に因数分解された形などいろいろ な形を取る。数学的に等価なものを見つけるのはかなり大変な作業になる。 そこで、 A, B の２つの数式の表現をそれぞれある中間の形 A', B' に直してその２つの表現 が一致していれば A, B は等価であるということにすると少しは楽になる。 ２つの多項式が等価であることを言う中間表現として 「展開形式で表し、係数は変数の前に置き、項を降冪の順に並べたもの」 を用いる。 こうすると２つの異なる表現は２つの異なる中間表現に対応 し、そのことを正準表現であると言う。

多項式を前置表現のまま正準表現に直す規則は複雑になる。 そこで多項式のみを表現する場合は、次のように連想リストを用いると処理が少し楽になる。 連想リスト構成要素のコンスセルは加算(+)で結合する。 連想リストの要素のコンスセルの car はキーと呼ばれ、 多項式表現では指数部の数字 n を格納することにする。 そして、 cdr には x^n の係数を格納する。 ・・・しかし、実際のプログラムでは処理の統一性のためにコンスセル ではなく、要素数 2 のリストで表現する。 連想リスト表現は前置表現よりも表現力に乏しいが、多項式の操作をするならば 十分であり、処理が楽になるというメリットがある。

(例)
多項式 a x^m + b x^n + c
連想リスト表現 ((m . a) (n . b) (0 . c))

表1 に前置表現で表された係数が 1 の単純な多項式を連想リスト表現に直す規則を示す。 係数が 1 でない場合は、乗算演算子(*)で表現されているので、 その処理は多項式の積とみなし、次に説明する多項式の乗算処理規則を利用して処理する。 表1-1,2,3 のように () を一つ余分に付けてコンスセルのリスト（要素数が1の連想リスト） にしているのは、後で append 関数でリストを結合していくためである。

変換規則
1 x → ((1 . 1))
2 atom → ((0 . atom))
3 (^ x n) → ((n . 1))
4 (+ a b) → ((alist a) (alist b))

表1: 展開された多項式の前置表現から連想リスト表現への変換

表2 に多項式の乗算を処理する規則を示す。 規則1 で左だけにコンスセルが残るようにし、 規則2 で全てをコンスセルの積に分解する。 そして、規則3 でコンスセル同士の乗算を行い、簡単化する。

変換規則
1 p=p1+p2+...+pn, ただし、 pi は x^i に対応するコンスセル
p * q → (+ (* p1 q) (* p2 q) ... (* pn q))
2 q=q1+q2+...+qn, ただし、 pi,qi は x^i に対応するコンスセル
pi * q → (+ (* pi q1) (* pi q2) ... (* pi qn))
3 pi,qi は x^i に対応するコンスセル
pi * qj → (i+j . (* (pi の係数) (qj の係数)))

表2: 連想リスト表現された多項式の乗算

次に表3 に示す規則で冪乗を処理する。

変換規則
1 p ^ 1 → p
2 p はアトムでないとき
p ^ 正整数n → p * p^(n-1)

表3: 連想リスト表現された多項式の冪乗

多項式を扱う Lisp プログラム

関数 機能
(pre2alist expr var) var の多項式の前置表現 expr を連想リスト表現にする
(alist2pre expr var) 多項式の連想リスト表現 expr を var の多項式の前置表現にする

プログラムリスト: polyalist.el 

;;;---------------------------------------------------------------
;;; 多項式の表現変換 (by 平野 拓一)
;;;---------------------------------------------------------------

;;;---------------------------------------------------------------
;;; 必要ファイル: in2pre.el, pre2in.el, derive.el, simplify.el
;;;---------------------------------------------------------------

;;; リストを1レベル平にする
(defun flatten1 (lis)
    (cond
        ; nil のとき
        ((null lis) nil)
        ; アトムのとき
        ; 次に nconc で要素連結するために list にしておく
        ((atom lis) (list lis))
        ; lis の先頭要素がアトムのとき
        ((atom (car lis))
         (nconc (list (car lis)) (flatten1 (cdr lis))))
        ; それ以外のとき
        (t (nconc (car lis) (flatten1 (cdr lis))))
    )
)

;;;---------------------------------------------------------------
;;; 多項式の表現変換をする
;;;---------------------------------------------------------------

;-----------------------------------------------------------------
; 展開された多項式の前置表現を連想リスト表現に変換する
;
; [Input]
; expr: 前置表現
; var: 多項式の文字
;
; [Return]
; 多項式の連想リスト表現
;-----------------------------------------------------------------
(defun pre2alist (expr var)
    (cond
        ; var のとき
        ; x → ((1 . 1))
        ((equal expr var) (list (list 1 1)))
        ; var でないアトムのとき
        ((atom expr) (list (list 0 expr)))
        ; + 演算子の処理
        ((equal (car expr) '+)
         (sort_collect (pre2alist_plus expr var)))
        ; * 演算子の処理
        ((equal (car expr) '*)
         (sort_collect (pre2alist_mult expr var)))
        ; ^ 演算子の処理
        ((equal (car expr) '^)
         (sort_collect (pre2alist_pow expr var)))
    )
)

(defun pre2alist_plus (expr var)
    (cond
        ; (+ a b) → ((alist a) (alist b))
        ; a=(cadr expr)
        ; b=(caddr expr)
        (t
         (append (pre2alist (cadr expr) var)
                 (pre2alist (caddr expr) var)))
    )
)

; p,q は多項式の連想リスト表現
(defun alist_mult (p q)
    (cond
        ; pi * qj → (i+j . (+ (pi の係数) (qj の係数)))
        ; pi=(cadr expr)
        ; qj=(caddr expr)
        ((and (eq (length p) 1)
              (eq (length q) 1))
         (list (list (simplify (list '+ (caar p) (caar q)))
                     (simplify (list '* (cdar p) (cdar q))))))
        ; pi * q → (+ (* pi q1) (* pi q2) ... (* pi qn))
        ((eq (length p) 1)
         (mapcar '(lambda (qj) (car (alist_mult p (list qj)))) q))
        ; p * qj → (+ (* p1 qj) (* p2 qj) ... (* pn qj))
        ((eq (length q) 1)
         (mapcar '(lambda (pi) (car (alist_mult (list pi) q))) p))
        ; p * q → (+ (* p1 q) (* p2 q) ... (* pn q))
        (t
         (flatten1 (mapcar '(lambda (pi) (alist_mult (list pi) q)) p)))
    )
)

; * 演算子の処理
(defun pre2alist_mult (expr var)
    (cond
        ; (* a b)
        ; a=(cadr expr)
        ; b=(caddr expr)
        (t (alist_mult (pre2alist (cadr expr) var)
                       (pre2alist (caddr expr) var)))
    )
)

(defun pre2alist_pow (expr var)
    (cond
        ; (^ x n) → ((n . 1))
        ;
        ; (^ a b)
        ; a=(cadr expr)
        ; b=(caddr expr)
        ((and (equal (cadr expr) var)
              (integerp (caddr expr)))
         (list (list (caddr expr) 1)))
        ; (^ p 1) → p
        ;
        ; (^ a b)
        ; a=(cadr expr)
        ; b=(caddr expr)
        ((eq (caddr expr) 1)
         (pre2alist (cadr expr) var))
        ; (^ p n) → (* p (^ p (- n 1)))
        ;
        ; (^ a b)
        ; a=(cadr expr)
        ; b=(caddr expr)
        ((and (> (length (cadr expr)) 1)
              (natnump (caddr expr)))
         (alist_mult (pre2alist (cadr expr) var)
                     (pre2alist (list '^
                                      (cadr expr)
                                      (simplify (list '-
                                                      (caddr expr)
                                                      1))) var)))
        ; その他の場合
        (t expr)
    )
)

;-----------------------------------------------------------------
; ソートして x^n の項はまとめる
;
; [Input]
; expr: 連想リスト表現
;-----------------------------------------------------------------
(defun sort_collect (expr)
    (let ((ord_prev -1) (p (sort expr 'sort_down_ord)) (expr2 ()))

         (while (not (null p))
             (if (equal (caar p) ord_prev)
                 ;---- true: 前と指数部が同じとき
                 (setq expr2
                       (append (list (list ord_prev
                                           ; 係数部の表現は簡単化しておく
                                           (simplify (list '+ (cdar expr2)
                                                              (cdar p)))))
                               (cdr expr2)))
                 ;---- false: 違う時
                 (setq expr2 (append (list (car p)) expr2))
             )

             (setq ord_prev (caar p))    ; 指数部の値を更新
             (setq p (cdr p))            ; 次のコンスセル
         )
         expr2
    )
)

; 降べきの順に並べるための比較関数
(defun sort_down_ord (cons1 cons2)
    (if (< (car cons1) (car cons2))
        t
        nil
    )
)

;-----------------------------------------------------------------
; 多項式の連想リスト表現を前置表現をに変換する
;
; [Input]
; expr: 多項式の連想リスト表現
; var: 多項式の文字
;
; [Return]
; 多項式の前置表現
;-----------------------------------------------------------------
(defun alist2pre (expr var)
    (cond
        ; 最後の項のとき
        ;
        ; ((a b))
        ; a=(caar expr)
        ; b=(car (cdar expr))
        ((eq (length expr) 1)
         (list '* (car (cdar expr))
                  (list '^ var (caar expr))))
        ; 項が２つ以上あるとき
        (t
         (list '+ (list '* (car (cdar expr))
                           (list '^ var (caar expr)))
                  (alist2pre (cdr expr) var)))
    )
)

;;;---------------------------------------------------------------
;;; 確認テスト
;;;---------------------------------------------------------------

; テスト関数

;(setq expr (in2pre '((x + a) ^ 2 + x * x)))
;(setq expr (in2pre '(a * x ^ 1 + b + x ^ 3)))
(setq expr (in2pre '((a * x + 1) ^ 2 + 1)))

; 多項式の前置表現から連想リスト表現へ
(pre2alist expr 'x)

; 多項式の連想リスト表現から前置表現へ
(pre2in (simplify (alist2pre (pre2alist expr 'x) 'y)))

;;
;; End of file
;;

実行例

入力 (setq expr (in2pre '((a * x + 1) ^ 2 + 1)))
(pre2alist expr 'x)
出力 ((2 (^ a 2)) (1 (* 2 a)) (0 2))
Go Back