\documentclass{article} \usepackage{open-axiom} \begin{document} \title{src/algebra prtition.spad} \author{William H. Burge} \maketitle \begin{abstract} \end{abstract} \tableofcontents \eject \section{domain PRTITION Partition} <>= import Integer import List )abbrev domain PRTITION Partition ++ Domain for partitions of positive integers ++ Author: William H. Burge ++ Date Created: 29 October 1987 ++ Date Last Updated: April 17, 2010 ++ Description: ++ 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}. ++ Keywords: ++ Examples: ++ References: Partition(): Exports == Implementation where macro L == List macro I == Integer macro OUT == OutputForm macro NNI == NonNegativeInteger macro UN == Union(%,"failed") Exports == Join(OrderedCancellationAbelianMonoid, ConvertibleTo List Integer,CoercibleTo List Integer) with partition: L I -> % ++ partition(li) converts a list of integers li to a partition powers: L I -> List Pair(I,PositiveInteger) ++ powers(li) returns a list of pairs. The second component of ++ each pair is the multiplicity with which the first component ++ occurs in li. 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 Implementation == add Rep == List Integer 0 == per nil coerce(s: %): List Integer == rep s convert x == copy rep x partition list == per sort(#2 < #1,list) zero? x == empty? rep x x < y == rep x < rep y x = y == rep x = rep y x + y == per merge(#2 < #1, rep x, rep y)$Rep n:NNI * x:% == zero? n => 0 x + (subtractIfCan(n,1) :: NNI) * x remv(i: I,x: %): UN == member?(i,rep x) => per remove(i, rep x)$Rep "failed" subtractIfCan(x, y) == zero? x => zero? y => 0 "failed" zero? y => x (aa := remv(first rep y,x)) case "failed" => "failed" subtractIfCan((aa :: %), per rest rep y) bite(i: I,li: L I): L I == empty? li => [0] first li = i => li1 := bite(i,rest li) cons(first(li1) + 1,rest li1) cons(0,li) powers l == empty? l => nil li := bite(first l,rest l) cons(pair(first l,first(li)::PositiveInteger + 1),powers(rest li)) conjugate x == per conjugate(rep x)$PartitionsAndPermutations mkterm(i1: I,i2: I): OUT == i2 = 1 => (i1 :: OUT) ** (" " :: OUT) (i1 :: OUT) ** (i2 :: OUT) mkexp1(lli: L Pair(I,PositiveInteger)): L OUT == empty? lli => nil li := first lli empty?(rest lli) and second(li) = 1 => [first(li) :: OUT] cons(mkterm(first li,second li),mkexp1(rest lli)) coerce(x:%):OUT == empty? rep x => rep(x)::OUT paren(reduce("*",mkexp1(powers rep x))) pdct x == */[factorial(second a) * (first(a) ** (second(a) pretend NNI)) for a in powers rep x] @ \section{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 +/[[[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 +/[[[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} <>= --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. @ <<*>>= <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}