diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ChangeLog | 6 | ||||
| -rw-r--r-- | src/algebra/prtition.spad.pamphlet | 129 |
2 files changed, 58 insertions, 77 deletions
diff --git a/src/ChangeLog b/src/ChangeLog index 087e5c42..16c4db0a 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,9 @@ +2010-04-17 Gabriel Dos Reis <gdr@cs.tamu.edu> + + * algebra/prtition.spad.pamphlet (Partition): Simplify + implementation. Reuse operations available from the + representation domain. + 2010-04-08 Gabriel Dos Reis <gdr@cs.tamu.edu> * algebra/boolean.spad.pamphlet (atoms$PropositionalFormula): diff --git a/src/algebra/prtition.spad.pamphlet b/src/algebra/prtition.spad.pamphlet index 5e70c34d..a340ef4d 100644 --- a/src/algebra/prtition.spad.pamphlet +++ b/src/algebra/prtition.spad.pamphlet @@ -20,22 +20,23 @@ import List ++ Domain for partitions of positive integers ++ Author: William H. Burge ++ Date Created: 29 October 1987 -++ Date Last Updated: 23 Sept 1991 +++ 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 - ++ 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, +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 @@ -52,92 +53,66 @@ Partition: Exports == Implementation where conjugate: % -> % ++ conjugate(p) returns the conjugate partition of a partition p - Implementation ==> add - - import PartitionsAndPermutations - - Rep := List Integer - 0 == nil() - - coerce (s:%): List Integer == 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)) + 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,%) -> UN - remv(i,x) == (member?(i,x) => dp(i,x); "failed") + remv(i: I,x: %): UN == + member?(i,rep x) => per remove(i, rep x)$Rep + "failed" subtractIfCan(x, y) == - empty? x => - empty? y => 0 + zero? x => + zero? y => 0 "failed" - empty? y => x - (aa := remv(first y,x)) case "failed" => "failed" - subtractIfCan((aa :: %), rest y) + zero? y => x + (aa := remv(first rep y,x)) case "failed" => "failed" + subtractIfCan((aa :: %), per rest rep y) - li1 : L I --!! 'bite' won't compile without this - bite: (I,L I) -> L I - bite(i,li) == - empty? li => concat(0,nil()) + bite(i: I,li: L I): L I == + empty? li => [0] first li = i => li1 := bite(i,rest li) - concat(first(li1) + 1,rest li1) - concat(0,li) + cons(first(li1) + 1,rest li1) + cons(0,li) - li : L I --!! 'powers' won't compile without this powers l == - empty? l => nil() + empty? l => nil li := bite(first l,rest l) - concat([first l,first(li) + 1],powers(rest li)) + cons([first l,first(li) + 1],powers(rest li)) - conjugate x == conjugate(x pretend Rep)$PartitionsAndPermutations + conjugate x == per conjugate(rep x)$PartitionsAndPermutations - mkterm: (I,I) -> OUT - mkterm(i1,i2) == + mkterm(i1: I,i2: I): OUT == i2 = 1 => (i1 :: OUT) ** (" " :: OUT) (i1 :: OUT) ** (i2 :: OUT) - mkexp1: L L I -> L OUT - mkexp1 lli == + mkexp1(lli: L L I): L OUT == 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)) + [first(li) :: OUT] + cons(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)))) + 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(x pretend Rep)] + for a in powers rep x] @ \section{domain SYMPOLY SymmetricPolynomial} @@ -146,7 +121,7 @@ Partition: Exports == Implementation where ++ Description: ++ This domain implements symmetric polynomial SymmetricPolynomial(R:Ring) == PolynomialRing(R,Partition) add - Term:= Record(k:Partition,c:R) + Term == Record(k:Partition,c:R) Rep:= List Term -- override PR implementation because coeff. arithmetic too expensive (??) |