\documentclass{article}
\usepackage{open-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
  macro NNI == NonNegativeInteger
  macro PI == PositiveInteger
 
  Exports ==> with
 
    conjugate: L PI -> L PI
      ++\spad{conjugate(pt)} is the conjugate of the partition pt.
    conjugates: ST L PI -> ST L PI
      ++\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
 
    -- nogreq(n,l) is the number of elements of l that are greater or
    -- equal to n
    nogreq: (I,L PI) -> I
    nogreq(n,x) == +/[1 for i in x | i >= n]
 
    conjugate x ==
      empty? x => empty()
      [nogreq(i,x)::PI 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}