(* SAC Combinatorical System Definition Module. *)

DEFINITION MODULE SACCOMB;


FROM MASSTOR IMPORT LIST;


PROCEDURE ASSPR(A: LIST;  VAR PL,ML: LIST); 
(*Assignment problem.  A is a square matrix of beta-integers, say
n by n.  p is an n-permutation for which the sum on i of
A(i,p(i)) is maximal, and m is this maximal sum.  All matrix
elements A(i,j) must be less than beta in absolute value.*)


PROCEDURE CSFPAR(L: LIST): LIST; 
(*Characteristic set from partition.  L is a list of non-negative beta-
integers (l sub 1, ...,l sub n).  C is a characteristic set, with j
belonging to C if and only if there is a subset I of the integers from
1 to n such that the sum of the l sub i with i in I=j.*)


PROCEDURE CSINT(A,B: LIST): LIST; 
(*Characteristic set intersection.  A and B are characteristic sets.
C is the intersection of A and B.*)


PROCEDURE CSSUB(A,B: LIST): LIST; 
(*Characteristic set subset.  A and B are characteristic sets.  t=1 if
A is a subset of B and otherwise t=0.*)


PROCEDURE CSUN(A,B: LIST): LIST; 
(*Characteristic set union.  A and B are characteristic sets.  C is the
union of A and B.*)


PROCEDURE DAND(AL,BL: LIST): LIST; 
(*Digit and.  a and b are non-negative beta-digits.  c is the
bit-wise and of a and b.*)


PROCEDURE DNIMP(AL,BL: LIST): LIST; 
(*Digit non-implication.  a and b are non-negative beta-digits.  c
is the bit-wise non-implication of a and b.*)


PROCEDURE DNOT(AL: LIST): LIST; 
(*Digit not.  a is a non-negative beta-digit.  b is the bit-wise
not of a.*)


PROCEDURE DOR(AL,BL: LIST): LIST; 
(*Digit or.  a and b are non-negative beta-digits.  c is the
bit-wise or of a and b.*)


PROCEDURE IBCIND(A,NL,KL: LIST): LIST; 
(*Integer binomial coefficient induction.  n and k are beta-integers
with 0 less than or equal to k less than or equal to n.  A is the
binomial coefficient n over k.  B is the binomial coefficient n
over k+1.*)


PROCEDURE IBCOEF(NL,KL: LIST): LIST; 
(*Integer binomial coefficient.  n and k are beta-integers with
0 less than or equal to k less than or equal to n.  A is the binomial
coefficient n over k.*)


PROCEDURE IBCPS(NL,KL: LIST): LIST; 
(*Integer binomial coefficient partial sum.  n and k are
beta integers, 0 le k le n.  A is the sum on i, from 0 to k, of the
binomial coefficient n over i.*)


PROCEDURE IFACTL(NL: LIST): LIST; 
(*Integer factorial.  n is a non-negative beta-integer.  A is
n factorial.*)


PROCEDURE LEXNEX(A: LIST): LIST; 
(*Lexicographically next.  A is a non-null list (a sub 1, ...,a sub m) 
such that a sub i is a non-null reductant of a sub i+1 for each
1 le i lt m.  B is the lexicographically next such list of the same
length, if one exists, and is () otherwise.*)


PROCEDURE LPERM(L,P: LIST): LIST; 
(*List permute.  L is a list (a sub 1, ...,a sub n).  P is a list
(p sub 1, ...,p sub n) of integers in the range 1, ...,n.  LP is the
list (a sub p sub 1, ...,a sub p sub n).*)


PROCEDURE PARTN(NL,P: LIST): LIST; 
(*Partition, next.  n is a positive beta-integer.  P is a partition of
n.  Q is the next partition of n after P in lexicographical order,
if any.  Otherwise Q=().*)


PROCEDURE PARTR(NL: LIST): LIST; 
(*Partition, random.  n is a positive beta-integer, n less than or
equal to 100.  P is a partition of n whose elements are the cycle
lengths of a random n-permutation.*)


PROCEDURE PARTSS(PL: LIST): LIST; 
(*Partition sumset.  p is a partition.  A is the sum set of p,
a characteristic set.*)


PROCEDURE PERMR(NL: LIST): LIST; 
(*Permutation, random.  n is a positive integer, n le 100.  L is a
list of the first n positive integers in random order.*)


PROCEDURE SDR(S: LIST;  VAR A,I: LIST); 
(*System of distinct representatives.  S is a list (s(1), ...,s(n)),
n ge 1, where each s(i) is a set of beta-integers represented as a
list.  Either A is a list (a(1), ...,a(n)) of distinct
representatives for (s(1), ...,s(n)) and I=(), or else A=() and
I=(i(1), ...,i(k)) is a subsequence of (1, ...,n) such that
(s(i(1)), ...,s(i(k))) has no system of distinct representatives.*)


PROCEDURE SFCS(A: LIST): LIST; 
(*Set from characteristic set.  A is a characteristic set.  B is the
same set represented as an increasing list of beta-integers.*)


END SACCOMB.