/usr/lib/open-axiom/src/algebra/partperm.spad is in open-axiom-source 1.4.1+svn~2626-2ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | --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.
)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])
|