aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/perman.spad.pamphlet
diff options
context:
space:
mode:
authordos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
committerdos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
commitab8cc85adde879fb963c94d15675783f2cf4b183 (patch)
treec202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/perman.spad.pamphlet
downloadopen-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz
Initial population.
Diffstat (limited to 'src/algebra/perman.spad.pamphlet')
-rw-r--r--src/algebra/perman.spad.pamphlet319
1 files changed, 319 insertions, 0 deletions
diff --git a/src/algebra/perman.spad.pamphlet b/src/algebra/perman.spad.pamphlet
new file mode 100644
index 00000000..bc2f63f1
--- /dev/null
+++ b/src/algebra/perman.spad.pamphlet
@@ -0,0 +1,319 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra perman.spad}
+\author{Johannes Grabmeier, Oswald Gschnitzer}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package GRAY GrayCode}
+<<package GRAY GrayCode>>=
+)abbrev package GRAY GrayCode
+++ Authors: Johannes Grabmeier, Oswald Gschnitzer
+++ Date Created: 7 August 1989
+++ Date Last Updated: 23 August 1990
+++ Basic Operations: nextSubsetGray
+++ Related Constructors: Permanent
+++ Also See: SymmetricGroupCombinatoric Functions
+++ AMS Classifications:
+++ Keywords: gray code, subsets of finite sets
+++ References:
+++ Henryk Minc: Evaluation of Permanents,
+++ Proc. of the Edinburgh Math. Soc.(1979), 22/1 pp 27-32.
+++ Nijenhuis and Wilf : Combinatorical Algorithms, Academic
+++ Press, New York 1978.
+++ S.G.Williamson, Combinatorics for Computer Science,
+++ Computer Science Press, 1985.
+++ Description:
+++ GrayCode provides a function for efficiently running
+++ through all subsets of a finite set, only changing one element
+++ by another one.
+GrayCode: public == private where
+
+ PI ==> PositiveInteger
+ I ==> Integer
+ V ==> Vector
+
+ public ==> with
+
+ nextSubsetGray: (V V I,PI) -> V V I
+ ++ nextSubsetGray(ww,n) returns a vector {\em vv} whose components
+ ++ have the following meanings:\begin{items}
+ ++ \item {\em vv.1}: a vector of length n whose entries are 0 or 1. This
+ ++ can be interpreted as a code for a subset of the set 1,...,n;
+ ++ {\em vv.1} differs from {\em ww.1} by exactly one entry;
+ ++ \item {\em vv.2.1} is the number of the entry of {\em vv.1} which
+ ++ will be changed next time;
+ ++ \item {\em vv.2.1 = n+1} means that {\em vv.1} is the last subset;
+ ++ trying to compute nextSubsetGray(vv) if {\em vv.2.1 = n+1}
+ ++ will produce an error!
+ ++ \end{items}
+ ++ The other components of {\em vv.2} are needed to compute
+ ++ nextSubsetGray efficiently.
+ ++ Note: this is an implementation of [Williamson, Topic II, 3.54,
+ ++ p. 112] for the special case {\em r1 = r2 = ... = rn = 2};
+ ++ Note: nextSubsetGray produces a side-effect, i.e.
+ ++ {\em nextSubsetGray(vv)} and {\em vv := nextSubsetGray(vv)}
+ ++ will have the same effect.
+
+ firstSubsetGray: PI -> V V I
+ ++ firstSubsetGray(n) creates the first vector {\em ww} to start a
+ ++ loop using {\em nextSubsetGray(ww,n)}
+
+ private ==> add
+
+ firstSubsetGray(n : PI) ==
+ vv : V V I := new(2,[])
+ vv.1 := new(n,0) : V I
+ vv.2 := new(n+1,1) : V I
+ for i in 1..(n+1) repeat
+ vv.2.i := i
+ vv
+
+ nextSubsetGray(vv : V V I,n : PI) ==
+ subs : V I := vv.1 -- subset
+ lab : V I := vv.2 -- labels
+ c : I := lab(1) -- element which is to be changed next
+ lab(1):= 1
+ if subs.c = 0 then subs.c := 1
+ else subs.c := 0
+ lab.c := lab(c+1)
+ lab(c+1) := c+1
+ vv
+
+@
+\section{package PERMAN Permanent}
+<<package PERMAN Permanent>>=
+)abbrev package PERMAN Permanent
+++ Authors: Johannes Grabmeier, Oswald Gschnitzer
+++ Date Created: 7 August 1989
+++ Date Last Updated: 23 August 1990
+++ Basic Operations: permanent
+++ Related Constructors: GrayCode
+++ Also See: MatrixLinearAlgebraFunctions
+++ AMS Classifications:
+++ Keywords: permanent
+++ References:
+++ Henryk Minc: Evaluation of Permanents,
+++ Proc. of the Edinburgh Math. Soc.(1979), 22/1 pp 27-32.
+++ Nijenhuis and Wilf : Combinatorical Algorithms, Academic
+++ Press, New York 1978.
+++ S.G.Williamson, Combinatorics for Computer Science,
+++ Computer Science Press, 1985.
+++ Description:
+++ Permanent implements the functions {\em permanent}, the
+++ permanent for square matrices.
+Permanent(n : PositiveInteger, R : Ring with commutative("*")):
+ public == private where
+ I ==> Integer
+ L ==> List
+ V ==> Vector
+ SM ==> SquareMatrix(n,R)
+ VECTPKG1 ==> VectorPackage1(I)
+ NNI ==> NonNegativeInteger
+ PI ==> PositiveInteger
+ GRAY ==> GrayCode
+
+ public ==> with
+
+ permanent: SM -> R
+ ++ permanent(x) computes the permanent of a square matrix x.
+ ++ The {\em permanent} is equivalent to
+ ++ the \spadfun{determinant} except that coefficients have
+ ++ no change of sign. This function
+ ++ is much more difficult to compute than the
+ ++ {\em determinant}. The formula used is by H.J. Ryser,
+ ++ improved by [Nijenhuis and Wilf, Ch. 19].
+ ++ Note: permanent(x) choose one of three algorithms, depending
+ ++ on the underlying ring R and on n, the number of rows (and
+ ++ columns) of x:\begin{items}
+ ++ \item 1. if 2 has an inverse in R we can use the algorithm of
+ ++ [Nijenhuis and Wilf, ch.19,p.158]; if 2 has no inverse,
+ ++ some modifications are necessary:
+ ++ \item 2. if {\em n > 6} and R is an integral domain with characteristic
+ ++ different from 2 (the algorithm works if and only 2 is not a
+ ++ zero-divisor of R and {\em characteristic()$R ^= 2},
+ ++ but how to check that for any given R ?),
+ ++ the local function {\em permanent2} is called;
+ ++ \item 3. else, the local function {\em permanent3} is called
+ ++ (works for all commutative rings R).
+ ++ \end{items}
+
+ private ==> add
+
+ -- local functions:
+
+ permanent2: SM -> R
+
+ permanent3: SM -> R
+
+ x : SM
+ a,b : R
+ i,j,k,l : I
+
+ permanent3(x) ==
+ -- This algorithm is based upon the principle of inclusion-
+ -- exclusion. A Gray-code is used to generate the subsets of
+ -- 1,... ,n. This reduces the number of additions needed in
+ -- every step.
+ sgn : R := 1
+ k : R
+ a := 0$R
+ vv : V V I := firstSubsetGray(n)$GRAY
+ -- For the meaning of the elements of vv, see GRAY.
+ w : V R := new(n,0$R)
+ j := 1 -- Will be the number of the element changed in subset
+ while j ^= (n+1) repeat -- we sum over all subsets of (1,...,n)
+ sgn := -sgn
+ b := sgn
+ if vv.1.j = 1 then k := -1
+ else k := 1 -- was that element deleted(k=-1) or added(k=1)?
+ for i in 1..(n::I) repeat
+ w.i := w.i +$R k *$R x(i,j)
+ b := b *$R w.i
+ a := a +$R b
+ vv := nextSubsetGray(vv,n)$GRAY
+ j := vv.2.1
+ if odd?(n) then a := -a
+ a
+
+
+ permanent(x) ==
+ -- If 2 has an inverse in R, we can spare half of the calcu-
+ -- lation needed in "permanent3": This is the algorithm of
+ -- [Nijenhuis and Wilf, ch.19,p.158]
+ n = 1 => x(1,1)
+ two : R := (2:I) :: R
+ half : Union(R,"failed") := recip(two)
+ if (half case "failed") then
+ if n < 7 then return permanent3(x)
+ else return permanent2(x)
+ sgn : R := 1
+ a := 0$R
+ w : V R := new(n,0$R)
+ -- w.i will be at first x.i and later lambda.i in
+ -- [Nijenhuis and Wilf, p.158, (24a) resp.(26)].
+ rowi : V R := new(n,0$R)
+ for i in 1..n repeat
+ rowi := row(x,i) :: V R
+ b := 0$R
+ for j in 1..n repeat
+ b := b + rowi.j
+ w.i := rowi(n) - (half*b)$R
+ vv : V V I := firstSubsetGray((n-1): PI)$GRAY
+ -- For the meaning of the elements of vv, see GRAY.
+ n :: I
+ b := 1
+ for i in 1..n repeat
+ b := b * w.i
+ a := a+b
+ j := 1 -- Will be the number of the element changed in subset
+ while j ^= n repeat -- we sum over all subsets of (1,...,n-1)
+ sgn := -sgn
+ b := sgn
+ if vv.1.j = 1 then k := -1
+ else k := 1 -- was that element deleted(k=-1) or added(k=1)?
+ for i in 1..n repeat
+ w.i := w.i +$R k *$R x(i,j)
+ b := b *$R w.i
+ a := a +$R b
+ vv := nextSubsetGray(vv,(n-1) : PI)$GRAY
+ j := vv.2.1
+ if not odd?(n) then a := -a
+ two * a
+
+ permanent2(x) ==
+ c : R := 0
+ sgn : R := 1
+ if (not (R has IntegralDomain))
+ -- or (characteristic()$R = (2:NNI))
+ -- compiler refuses to compile the line above !!
+ or (sgn + sgn = c)
+ then return permanent3(x)
+ -- This is a slight modification of permanent which is
+ -- necessary if 2 is not zero or a zero-divisor in R, but has
+ -- no inverse in R.
+ n = 1 => x(1,1)
+ two : R := (2:I) :: R
+ a := 0$R
+ w : V R := new(n,0$R)
+ -- w.i will be at first x.i and later lambda.i in
+ -- [Nijenhuis and Wilf, p.158, (24a) resp.(26)].
+ rowi : V R := new(n,0$R)
+ for i in 1..n repeat
+ rowi := row(x,i) :: V R
+ b := 0$R
+ for j in 1..n repeat
+ b := b + rowi.j
+ w.i := (two*(rowi(n)))$R - b
+ vv : V V I := firstSubsetGray((n-1): PI)$GRAY
+ n :: I
+ b := 1
+ for i in 1..n repeat
+ b := b *$R w.i
+ a := a +$R b
+ j := 1 -- Will be the number of the element changed in subset
+ while j ^= n repeat -- we sum over all subsets of (1,...,n-1)
+ sgn := -sgn
+ b := sgn
+ if vv.1.j = 1 then k := -1
+ else k := 1 -- was that element deleted(k=-1) or added(k=1)?
+ c := k * two
+ for i in 1..n repeat
+ w.i := w.i +$R c *$R x(i,j)
+ b := b *$R w.i
+ a := a +$R b
+ vv := nextSubsetGray(vv,(n-1) : PI)$GRAY
+ j := vv.2.1
+ if not odd?(n) then a := -a
+ b := two ** ((n-1):NNI)
+ (a exquo b) :: R
+
+@
+\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>>
+
+<<package GRAY GrayCode>>
+<<package PERMAN Permanent>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}