/usr/share/axiom-20170501/src/algebra/PARTPERM.spad is in axiom-source 20170501-3.
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 | )abbrev package PARTPERM PartitionsAndPermutations
++ Author: William H. Burge
++ Date Created: 29 October 1987
++ Date Last Updated: 3 April 1991
++ Description:
++ PartitionsAndPermutations contains functions for generating streams of
++ integer partitions, and streams of sequences of integers
++ composed from a multi-set.
PartitionsAndPermutations() : SIG == CODE where
I ==> Integer
L ==> List
ST ==> Stream
ST1 ==> StreamFunctions1
ST2 ==> StreamFunctions2
ST3 ==> StreamFunctions3
SIG ==> 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, 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}.
CODE ==> 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((l1:List(I)):List(I)+->concat(N,l1),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((l1:List(I)):List(I)+->concat(first x,l1),shuffle(rest x,y)),_
map((l2:List(I)):List(I)+->concat(first y,l2),shuffle(x,rest y)))
shufflein(x,yy) ==
concat(map((l1:List(I)):ST(L I)+->shuffle(x,l1),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])
|