\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} <>= )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 partitions: (NNI,NNI,NNI) -> ST L PI ++\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: NNI -> ST L PI ++\spad{partitions(n)} is the stream of all partitions of n. partitions: (NNI,NNI) -> ST L PI ++\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 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 partitions(M,N,n) == zero? n => concat(empty()$L(PI),empty()$(ST L PI)) zero? M or zero? N or n < N => empty() s := partitions(subtractIfCan(M,1)::NNI,N,subtractIfCan(n,N)::NNI) c := map(concat(N::PI,#1),s) concat(c,partitions(M,subtractIfCan(N,1)::NNI,n)) partitions n == partitions(n,n,n) partitions(M,N)== aaa : L ST L PI := [partitions(M,N,i) for i in 0..M*N] concat(aaa :: ST ST L PI)$ST1(L PI) -- 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} <>= --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. @ <<*>>= <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}