/usr/share/axiom-20170501/src/algebra/SETMN.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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 | )abbrev domain SETMN SetOfMIntegersInOneToN
++ Author: Manuel Bronstein
++ Date Created: 10 January 1994
++ Date Last Updated: 10 January 1994
++ Description:
++ \spadtype{SetOfMIntegersInOneToN} implements the subsets of M integers
++ in the interval \spad{[1..n]}
SetOfMIntegersInOneToN(m, n) : SIG == CODE where
n : PositiveInteger
m : PositiveInteger
PI ==> PositiveInteger
N ==> NonNegativeInteger
U ==> Union(%, "failed")
SIG ==> Finite with
incrementKthElement : (%, PI) -> U
++ incrementKthElement(S,k) increments the k^{th} element of S,
++ and returns "failed" if the result is not a set of M integers
++ in \spad{1..n} any more.
replaceKthElement : (%, PI, PI) -> U
++ replaceKthElement(S,k,p) replaces the k^{th} element of S by p,
++ and returns "failed" if the result is not a set of M integers
++ in \spad{1..n} any more.
elements : % -> List PI
++ elements(S) returns the list of the elements of S in increasing order.
setOfMinN : List PI -> %
++ setOfMinN([a_1,...,a_m]) returns the set {a_1,...,a_m}.
++ Error if {a_1,...,a_m} is not a set of M integers in \spad{1..n}.
enumerate : () -> Vector %
++ enumerate() returns a vector of all the sets of M integers in
++ \spad{1..n}.
member? : (PI, %) -> Boolean
++ member?(p, s) returns true is p is in s, false otherwise.
delta : (%, PI, PI) -> N
++ delta(S,k,p) returns the number of elements of S which are strictly
++ between p and the k^{th} element of S.
CODE ==> add
Rep := Record(bits:Bits, pos:N)
reallyEnumerate: () -> Vector %
enum: (N, N, PI) -> List Bits
all:Reference Vector % := ref empty()
sz:Reference N := ref 0
s1 = s2 == s1.bits =$Bits s2.bits
coerce(s:%):OutputForm == brace [i::OutputForm for i in elements s]
random() == index((1 + (random()$Integer rem size()))::PI)
reallyEnumerate() == [[b, i] for b in enum(m, n, n) for i in 1..]
member?(p, s) == s.bits.p
enumerate() ==
if empty? all() then all() := reallyEnumerate()
all()
-- enumerates the sets of p integers in 1..q, returns them as sets in 1..n
-- must have p <= q
enum(p, q, n) ==
zero? p or zero? q => empty()
p = q =>
b := new(n, false)$Bits
for i in 1..p repeat b.i := true
[b]
q1 := (q - 1)::N
l := enum((p - 1)::N, q1, n)
if empty? l then l := [new(n, false)$Bits]
for s in l repeat s.q := true
concat_!(enum(p, q1, n), l)
size() ==
if zero? sz() then
sz() := binomial(n, m)$IntegerCombinatoricFunctions(Integer) :: N
sz()
lookup s ==
if empty? all() then all() := reallyEnumerate()
if zero?(s.pos) then s.pos := position(s, all()) :: N
s.pos :: PI
index p ==
p > size() => error "index: argument too large"
if empty? all() then all() := reallyEnumerate()
all().p
setOfMinN l ==
s := new(n, false)$Bits
count:N := 0
for i in l repeat
count := count + 1
count > m or zero? i or i > n or s.i =>
error "setOfMinN: improper set of integers"
s.i := true
count < m => error "setOfMinN: improper set of integers"
[s, 0]
elements s ==
b := s.bits
l:List PI := empty()
found:N := 0
i:PI := 1
while found < m repeat
if b.i then
l := concat(i, l)
found := found + 1
i := i + 1
reverse_! l
incrementKthElement(s, k) ==
b := s.bits
found:N := 0
i:N := 1
while found < k repeat
if b.i then found := found + 1
i := i + 1
i > n or b.i => "failed"
newb := copy b
newb.i := true
newb.((i-1)::N) := false
[newb, 0]
delta(s, k, p) ==
b := s.bits
count:N := found:N := 0
i:PI := 1
while found < k repeat
if b.i then
found := found + 1
if i > p and found < k then count := count + 1
i := i + 1
count
replaceKthElement(s, k, p) ==
b := s.bits
found:N := 0
i:PI := 1
while found < k repeat
if b.i then found := found + 1
if found < k then i := i + 1
b.p and i ^= p => "failed"
newb := copy b
newb.p := true
newb.i := false
[newb, (i = p => s.pos; 0)]
|