Initial population.

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}