(* ---------------------------------------------------------------------------- * $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- *)