diff options
Diffstat (limited to 'src/algebra/prtition.spad.pamphlet')
| -rw-r--r-- | src/algebra/prtition.spad.pamphlet | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/src/algebra/prtition.spad.pamphlet b/src/algebra/prtition.spad.pamphlet new file mode 100644 index 00000000..6b3cd538 --- /dev/null +++ b/src/algebra/prtition.spad.pamphlet @@ -0,0 +1,218 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra prtition.spad} +\author{William H. Burge} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{domain PRTITION Partition} +<<domain PRTITION Partition>>= +)abbrev domain PRTITION Partition +++ Domain for partitions of positive integers +++ Author: William H. Burge +++ Date Created: 29 October 1987 +++ Date Last Updated: 23 Sept 1991 +++ Keywords: +++ Examples: +++ References: +Partition: Exports == Implementation where + ++ Partition is an OrderedCancellationAbelianMonoid which is used + ++ as the basis for symmetric polynomial representation of the + ++ sums of powers in SymmetricPolynomial. Thus, \spad{(5 2 2 1)} will + ++ represent \spad{s5 * s2**2 * s1}. + L ==> List + I ==> Integer + OUT ==> OutputForm + NNI ==> NonNegativeInteger + UN ==> Union(%,"failed") + + Exports ==> Join(OrderedCancellationAbelianMonoid, + ConvertibleTo List Integer) with + partition: L I -> % + ++ partition(li) converts a list of integers li to a partition + powers: L I -> L L I + ++ powers(li) returns a list of 2-element lists. For each 2-element + ++ list, the first element is an entry of li and the second + ++ element is the multiplicity with which the first element + ++ occurs in li. There is a 2-element list for each value + ++ occurring in l. + pdct: % -> I + ++ \spad{pdct(a1**n1 a2**n2 ...)} returns + ++ \spad{n1! * a1**n1 * n2! * a2**n2 * ...}. + ++ This function is used in the package \spadtype{CycleIndicators}. + conjugate: % -> % + ++ conjugate(p) returns the conjugate partition of a partition p + coerce:% -> List Integer + ++ coerce(p) coerces a partition into a list of integers + + Implementation ==> add + + import PartitionsAndPermutations + + Rep := List Integer + 0 == nil() + + coerce (s:%) == s pretend List Integer + convert x == copy(x pretend L I) + + partition list == sort(#2 < #1,list) + + x < y == + empty? x => not empty? y + empty? y => false + first x = first y => rest x < rest y + first x < first y + + x = y == + EQUAL(x,y)$Lisp +-- empty? x => empty? y +-- empty? y => false +-- first x = first y => rest x = rest y +-- false + + x + y == + empty? x => y + empty? y => x + first x > first y => concat(first x,rest(x) + y) + concat(first y,x + rest(y)) + n:NNI * x:% == (zero? n => 0; x + (subtractIfCan(n,1) :: NNI) * x) + + dp: (I,%) -> % + dp(i,x) == + empty? x => 0 + first x = i => rest x + concat(first x,dp(i,rest x)) + + remv: (I,%) -> UN + remv(i,x) == (member?(i,x) => dp(i,x); "failed") + + subtractIfCan(x, y) == + empty? x => + empty? y => 0 + "failed" + empty? y => x + (aa := remv(first y,x)) case "failed" => "failed" + subtractIfCan((aa :: %), rest y) + + li1 : L I --!! 'bite' won't compile without this + bite: (I,L I) -> L I + bite(i,li) == + empty? li => concat(0,nil()) + first li = i => + li1 := bite(i,rest li) + concat(first(li1) + 1,rest li1) + concat(0,li) + + li : L I --!! 'powers' won't compile without this + powers l == + empty? l => nil() + li := bite(first l,rest l) + concat([first l,first(li) + 1],powers(rest li)) + + conjugate x == conjugate(x pretend Rep)$PartitionsAndPermutations + + mkterm: (I,I) -> OUT + mkterm(i1,i2) == + i2 = 1 => (i1 :: OUT) ** (" " :: OUT) + (i1 :: OUT) ** (i2 :: OUT) + + mkexp1: L L I -> L OUT + mkexp1 lli == + empty? lli => nil() + li := first lli + empty?(rest lli) and second(li) = 1 => + concat(first(li) :: OUT,nil()) + concat(mkterm(first li,second li),mkexp1(rest lli)) + + coerce(x:%):OUT == + empty? (x pretend Rep) => coerce(x pretend Rep)$Rep + paren(reduce("*",mkexp1(powers(x pretend Rep)))) + + pdct x == + */[factorial(second a) * (first(a) ** (second(a) pretend NNI)) + for a in powers(x pretend Rep)] + +@ +\section{domain SYMPOLY SymmetricPolynomial} +<<domain SYMPOLY SymmetricPolynomial>>= +)abbrev domain SYMPOLY SymmetricPolynomial +++ Description: +++ This domain implements symmetric polynomial +SymmetricPolynomial(R:Ring) == PolynomialRing(R,Partition) add + Term:= Record(k:Partition,c:R) + Rep:= List Term + +-- override PR implementation because coeff. arithmetic too expensive (??) + + if R has EntireRing then + (p1:%) * (p2:%) == + null p1 => 0 + null p2 => 0 + zero?(p1.first.k) => p1.first.c * p2 +-- one? p2 => p1 + (p2 = 1) => p1 + +/[[[t1.k+t2.k,t1.c*t2.c]$Term for t2 in p2] + for t1 in reverse(p1)] + -- This 'reverse' is an efficiency improvement: + -- reduces both time and space [Abbott/Bradford/Davenport] + else + (p1:%) * (p2:%) == + null p1 => 0 + null p2 => 0 + zero?(p1.first.k) => p1.first.c * p2 +-- one? p2 => p1 + (p2 = 1) => p1 + +/[[[t1.k+t2.k,r]$Term for t2 in p2 | (r:=t1.c*t2.c) ^= 0] + for t1 in reverse(p1)] + -- This 'reverse' is an efficiency improvement: + -- reduces both time and space [Abbott/Bradford/Davenport] + +@ +\section{License} +<<license>>= +--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. +--All rights reserved. +-- +--Redistribution and use in source and binary forms, with or without +--modification, are permitted provided that the following conditions are +--met: +-- +-- - Redistributions of source code must retain the above copyright +-- notice, this list of conditions and the following disclaimer. +-- +-- - Redistributions in binary form must reproduce the above copyright +-- notice, this list of conditions and the following disclaimer in +-- the documentation and/or other materials provided with the +-- distribution. +-- +-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the +-- names of its contributors may be used to endorse or promote products +-- derived from this software without specific prior written permission. +-- +--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +@ +<<*>>= +<<license>> + +<<domain PRTITION Partition>> +<<domain SYMPOLY SymmetricPolynomial>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |