Initial population.

1 files changed, 168 insertions, 0 deletions

diff --git a/src/algebra/partperm.spad.pamphlet b/src/algebra/partperm.spad.pamphlet
new file mode 100644
index 00000000..cbe68098
--- /dev/null
+++ b/src/algebra/partperm.spad.pamphlet
@@ -0,0 +1,168 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra partperm.spad}
+\author{William Burge}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package PARTPERM PartitionsAndPermutations}
+<<package PARTPERM PartitionsAndPermutations>>=
+)abbrev package PARTPERM PartitionsAndPermutations
+++ Author: William H. Burge
+++ Date Created: 29 October 1987
+++ Date Last Updated: 3 April 1991
+++ Basic Operations:
+++ Related Domains:
+++ Also See:
+++ AMS Classifications:
+++ Keywords: partition, permutation
+++ References:
+++ Description: PartitionsAndPermutations contains
+++ functions for generating streams of integer partitions,
+++ and streams of sequences of integers
+++ composed from a multi-set.
+PartitionsAndPermutations: Exports == Implementation where
+  I   ==> Integer
+  L   ==> List
+  ST  ==> Stream
+  ST1 ==> StreamFunctions1
+  ST2 ==> StreamFunctions2
+  ST3 ==> StreamFunctions3
+ 
+  Exports ==> with
+ 
+    partitions: (I,I,I) -> ST L I
+      ++\spad{partitions(p,l,n)} is the stream of partitions
+      ++ of n whose number of parts is no greater than p
+      ++ and whose largest part is no greater than l.
+    partitions: I -> ST L I
+      ++\spad{partitions(n)} is the stream of all partitions of n.
+    partitions: (I,I) -> ST L I
+      ++\spad{partitions(p,l)} is the stream of all
+      ++ partitions whose number of
+      ++ parts and largest part are no greater than p and l.
+    conjugate: L I -> L I
+      ++\spad{conjugate(pt)} is the conjugate of the partition pt.
+    conjugates: ST L I -> ST L I
+      ++\spad{conjugates(lp)} is the stream of conjugates of a stream
+      ++ of partitions lp.
+    shuffle: (L I,L I) -> ST L I
+      ++\spad{shuffle(l1,l2)} forms the stream of all shuffles of l1
+      ++ and l2, i.e. all sequences that can be formed from
+      ++ merging l1 and l2.
+    shufflein: (L I,ST L I) -> ST L I
+      ++\spad{shufflein(l,st)} maps shuffle(l,u) on to all
+      ++ members u of st, concatenating the results.
+    sequences: (L I,L I) -> ST L I
+      ++\spad{sequences(l1,l2)} is the stream of all sequences that
+      ++ can be composed from the multiset defined from
+      ++ two lists of integers l1 and l2.
+      ++ For example,the pair \spad{([1,2,4],[2,3,5])} represents
+      ++ multi-set with 1 \spad{2}, 2 \spad{3}'s, and 4 \spad{5}'s.
+    sequences: L I -> ST L I
+      ++ \spad{sequences([l0,l1,l2,..,ln])} is the set of
+      ++  all sequences formed from
+      ++ \spad{l0} 0's,\spad{l1} 1's,\spad{l2} 2's,...,\spad{ln} n's.
+    permutations: I -> ST L I
+      ++\spad{permutations(n)} is the stream of permutations
+      ++ formed from \spad{1,2,3,...,n}.
+ 
+  Implementation ==> add
+ 
+    partitions(M,N,n) ==
+      zero? n => concat(empty()$L(I),empty()$(ST L I))
+      zero? M or zero? N or n < 0 => empty()
+      c := map(concat(N,#1),partitions(M - 1,N,n - N))
+      concat(c,partitions(M,N - 1,n))
+ 
+    partitions n == partitions(n,n,n)
+ 
+    partitions(M,N)==
+      aaa : L ST L I := [partitions(M,N,i) for i in 0..M*N]
+      concat(aaa :: ST ST L I)$ST1(L I)
+ 
+    -- nogreq(n,l) is the number of elements of l that are greater or
+    -- equal to n
+    nogreq: (I,L I) -> I
+    nogreq(n,x) == +/[1 for i in x | i >= n]
+ 
+    conjugate x ==
+      empty? x => empty()
+      [nogreq(i,x) for i in 1..first x]
+ 
+    conjugates z == map(conjugate,z)
+ 
+    shuffle(x,y)==
+      empty? x => concat(y,empty())$(ST L I)
+      empty? y => concat(x,empty())$(ST L I)
+      concat(map(concat(first x,#1),shuffle(rest x,y)),_
+             map(concat(first y,#1),shuffle(x,rest y)))
+ 
+    shufflein(x,yy) ==
+      concat(map(shuffle(x,#1),yy)$ST2(L I,ST L I))$ST1(L I)
+ 
+    -- rpt(n,m) is the list of n m's
+    rpt: (I,I) -> L I
+    rpt(n,m) == [m for i in 1..n]
+ 
+    -- zrpt(x,y) where x is [x0,x1,x2...] and y is [y0,y1,y2...]
+    -- is the stream [rpt(x0,y0),rpt(x1,y1),...]
+    zrpt: (L I,L I) -> ST L I
+    zrpt(x,y) == map(rpt,x :: ST I,y :: ST I)$ST3(I,I,L I)
+ 
+    sequences(x,y) ==
+      reduce(concat(empty()$L(I),empty()$(ST L I)),_
+                    shufflein,zrpt(x,y))$ST2(L I,ST L I)
+ 
+    sequences x == sequences(x,[i for i in 0..#x-1])
+ 
+    permutations n == sequences(rpt(n,1),[i for i in 1..n])
+
+@
+\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 PARTPERM PartitionsAndPermutations>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}