________________________________
De: Barton Willis <willisb at unk.edu>
Para: Richard Fateman <fateman at eecs.berkeley.edu>
CC: "maxima at math.utexas.edu" <maxima at math.utexas.edu>
Enviado: S?bado 22 de diciembre de 2012 21:48
Asunto: Re: [Maxima] properties & assume equal
> Barton's proposal seems to require some loop-avoidance fiddling, I think.
> RJF
Yeah, maybe the reason the author of check-noninteger-facts didn't make look at only one ply was fear of infinite loops.
Bart
;; given a set S and some pairs of elements of S compute
;; the equivalence relation generated by those pairs.
;; eqclasses is a hash-table whose values are the classes and
;; each? key is a canonical elements for each class
(setq *eqc* (make-hash-table))
(defparameter *eqclasses* nil)
(defun gethash-force(key)
? (multiple-value-bind (val exists) (gethash key *eqc*)
??? (if exists val
??? (setf (gethash key *eqc*) key))))
(defun put-eq (a b)
? (setf (gethash (gethash-force a) *eqc*)
??? (gethash (gethash-force b) *eqc*)))
(defun show-hash(h)
? (maphash (lambda(k v) (format t "~s => ~s~%" k v)) h))
(defun hash-keys(h)
? (loop for k being each hash-key of h collect k))
(defun compact()?
? (loop for k in (hash-keys *eqc*) do
?????? (loop for?? x = (gethash k *eqc*) then y
???????????? for?? y = (gethash x *eqc*)? until (eq x y)
???????? finally (setf (gethash k *eqc*) x))))
??? ???
(defun classes()
? (let (v)
? (setq *eqclasses* (make-hash-table))
? (loop for k being each hash-key of *eqc* do
?????? (setf v (gethash k *eqc*)
??? ???? (gethash v *eqclasses*) (cons k (gethash v *eqclasses*))))))
(defun example()
? (mapcar (lambda(x) (put-eq (first x)(second x)))
??? ? '((one two) (three two) (four five) (seven eight) (eight nine)))
? (compact)
? (classes)
? (show-hash *eqclasses*))
given
eq(one,two), eq(three,two), eq(four,five) eq(seven,eight) eq(eight,nine)
the runtime of this code should be linear in the number of elements of the setof atoms.
CL-USER> (example)
TWO => (THREE TWO ONE)
FIVE => (FIVE FOUR)
NINE => (NINE EIGHT SEVEN)
_______________________________________________
Maxima mailing list
Maxima at math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima