DEFINITION MODULE CombLib;
(*------------------------------------------------------------------------*)
(* Combination of numbers / Kombinatorische Routinen *)
(*------------------------------------------------------------------------*)
(* Implementation : Michael Riedl *)
(* Licence : GNU Lesser General Public License (LGPL) *)
(*------------------------------------------------------------------------*)
(* $Id: CombLib.def,v 1.1 2018/12/10 09:14:34 mriedl Exp mriedl $ *)
PROCEDURE NoverK(N,K : INTEGER) : LONGREAL;
(*----------------------------------------------------------------*)
(* Der Binomialkoeffizient {N ueber K} gibt an, auf wie viele *)
(* verschiedene Arten man K Objekte aus einer Menge von N *)
(* verschiedenen Objekten ohne Zur"ucklegen und ohne Beachtung *)
(* der Reihenfolge ausw"ahlen kann. *)
(* *)
(* Computes the combinatorial coefficient C(N,K) = {N \over K} *)
(* C(N,K) is the number of distinct combinations of K objects *)
(* chosen from a set of N distinct objects. Within a combination *)
(* the order does not matter. *)
(* *)
(* c(N,K) := N! / ( (N-K)! * K! ) = {N \over K} *)
(* *)
(* This procedure is base on subroutine comnin of John Burkardt *)
(*----------------------------------------------------------------*)
PROCEDURE Combination(VAR Comb : ARRAY OF ARRAY OF SHORTCARD;
VAR NComb : INTEGER;
NSet : INTEGER;
IMax : INTEGER;
VAR iFehl : INTEGER);
(*----------------------------------------------------------------*)
(* Combinations without repetition and without importantce of *)
(* order. The routine generates all possible combinations of the *)
(* integers from 1 to IMax, taken NSet elementa at a time, *)
(* storing the results in the 2-D array Comb, which has a first *)
(* dimension of NComb and a second dimension of NSet *)
(* *)
(* The number of combinations NComb is given by / *)
(* Die Anzahl der Kombinationen ergibt sich zu *)
(* *)
(* NComb = IMax! / ((IMax - NSet)! * NSet!) = {IMax \over NSet} *)
(* *)
(* Auswahl von NSet Elementen aus IMax Elementen ohne *)
(* Wiederholungen und ohne Ber"ucksichtigung der Reihenfolge *)
(* *)
(* <== Comb : Berechneten Kombinationen (Comb[NComb,NSet]) *)
(* <== NComb : Anzahl der berechneten Kombinationen *)
(* ==> NSet : Anzahl der zu kombinierenden Ganzzahlen *)
(* ==> IMax : H"ochster Index der zu kombinierenden Ganzzahlen *)
(* i = 1,IMax *)
(* <== iFehl : Ist ungleich Null wenn Comb nicht ausreichend *)
(* Dimensioniert ist *)
(*----------------------------------------------------------------*)
PROCEDURE NextP( N : INTEGER;
VAR A : ARRAY OF INTEGER) : BOOLEAN;
(*----------------------------------------------------------------*)
(* Berechnet die naechste Permutation von N Elementen. Wenn die *)
(* letzte moegliche Permutation berechnet wurde wird "falsch" *)
(* zurueckgegeben. Initial muss der Vektor A mit den Zahlen 1 bis *)
(* N vorbelegt werden. Insgesamt werden N! Permutationen *)
(* berechnet. Die folgende Testroutine wuerde die Permutation der *)
(* Zahlen von 1 bis 3 ausgeben: *)
(* *)
(* MODULE TstNextP; *)
(* *)
(* FROM CombLib IMPORT NextP; *)
(* IMPORT TIO; *)
(* *)
(* CONST N = 3; *)
(* *)
(* VAR i : INTEGER; *)
(* A : ARRAY [1..N] OF INTEGER; *)
(* BEGIN *)
(* FOR i:=1 TO N DO A[i]:=i; END; *)
(* REPEAT *)
(* FOR i:=1 TO N DO TIO.WrInt(A[i],5); END; TIO.WrLn; *)
(* UNTIL NOT NextP(N,A); *)
(* END TstNextP. *)
(* *)
(* Calculates the next permutation of N elements. If the last *)
(* permutaion had been calculated the procedure will return *)
(* "false". Before the first call the integer array A has to be *)
(* initialized with the numbers 1 to N. The number of *)
(* permutations returned will be N!. The sample code above *)
(* would print all permutations of the numbers 1,2 and 3. *)
(*----------------------------------------------------------------*)
PROCEDURE CombNK(N,K : CARDINAL) : CARDINAL;
(* ---------------------------------------------------------------*)
(* Returns the number of combinations of N things taken K at a *)
(* time or 0 if the parameters are incompatible *)
(* Based on code found in Applied Statistics Algorithm AS304 *)
(* This procedure is an alternative to NoverK *)
(* ---------------------------------------------------------------*)
END CombLib.