```(* ----------------------------------------------------------------------------
* \$Id: SACCOMB.md,v 1.2 1992/02/12 13:19:07 pesch Exp \$
* ----------------------------------------------------------------------------
* This file is part of MAS.
* ----------------------------------------------------------------------------
* Copyright (c) 1989 - 1992 Universitaet Passau
* ----------------------------------------------------------------------------
* \$Log: SACCOMB.md,v \$
* Revision 1.2  1992/02/12  13:19:07  pesch
* Moved CONST Definition to the right place.
*
* Revision 1.1  1992/01/22  15:08:10  kredel
* Initial revision
*
* ----------------------------------------------------------------------------
*)

DEFINITION MODULE SACCOMB;

(* SAC Combinatorical System Definition Module. *)

FROM MASSTOR IMPORT LIST;

CONST rcsid = "\$Id: SACCOMB.md,v 1.2 1992/02/12 13:19:07 pesch Exp \$";
CONST copyright = "Copyright (c) 1989 - 1992 Universitaet Passau";

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.

(* -EOF- *)
```