Combinations and permutations

This page uses content from Wikipedia. The original article was at Combination. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

This page uses content from Wikipedia. The original article was at Permutation. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Implement a Combination ⁿC_k and Permutation ⁿP_k Operators in the target language:

$^{n}C_{k}={\binom {n}{k}}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}$
$^{n}P_{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$

c.f. Wikipedia for a full explanation.

To test, generate examples of:

Permutations from 1 to 12 and Combinations from 10 to 60 using Integer arithmetic.
Permutations from 5 to 15000 and Combinations from 100 to 1000 using Floating point arithmetic.

ALGOL 68

Works with: ALGOL 68 version Revision 1 - one minor extension to language used - PRAGMA READ, similar to C's #include directive.

Works with: ALGOL 68G version Any - tested with release algol68g-2.6.

File: prelude_combinations_and_permutations.a68<lang algol68># -*- coding: utf-8 -*- #

CO REQUIRES

 MODE CPINT = #LONG# INT;
 MODE CPOUT = #LONG# INT; # the answer, can be REAL #
 MODE CPREAL = REAL; # the answer, can be REAL #
 MODE CPARGS = STRUCT(CHAR name, #REF# CPINT n,k);
 PROC cp fix value error = (#REF# CPARGS args)BOOL: ...

END CO

PRIO C = 8, P = 8; # should be 7.5, a priority between *,/ and **,SHL,SHR etc #

I suspect there is a more reliable way of doing this using the Gamma Function approx #

OP P = (CPINT n, r)CPOUT: (

 IF n < r ORF r < 0 THEN IF NOT cp fix value error(CPARGS("P",n,r)) THEN stop FI FI;
 CPOUT out := 1;

basically nPk = (n-r+1)(n-r+2)...(n-2)(n-1)n = n!/(n-r+1)! #

 FOR i FROM n-r+1 TO n DO out *:= i OD;
 out

);

A real version, a better way (probably) would be to use the gamma function #

OP P = (CPREAL n, r)CPREAL: (

 IF n < r ORF r < 0 THEN IF NOT cp fix value error(CPARGS("P",ENTIER n,ENTIER r)) THEN stop FI FI;
 CPREAL out := 1;

basically nPk = (n-r+1)(n-r+2)...(n-2)(n-1)n = n!/(n-r+1)! #

 CPREAL i := n-r+1;
 WHILE i <= n DO
   out*:= i;

a crude check for underflow #

   IF i = i + 1 THEN IF NOT cp fix value error(CPARGS("P",ENTIER n,ENTIER r)) THEN stop FI FI;
   i+:=1
 OD;
 out

);

basically C(n,r) = nCk = nPk/r! = n!/(n-r)!/r! #

OP C = (CPINT n, r)CPOUT: (

 IF n < r ORF r < 0 THEN IF NOT cp fix value error(("C",n,r)) THEN stop FI FI;
 CPINT largest = ( r > n - r | r | n - r );
 CPINT smallest = n - largest;
 CPOUT out := 1;
 INT smaller fact := 2;
 FOR larger fact FROM largest+1 TO n DO

try and prevent overflow, p.s. there must be a smarter way to do this #

   out *:= larger fact;
   WHILE smaller fact <= smallest ANDF out MOD smaller fact = 0 DO 
     out OVERAB smaller fact;
     smaller fact +:= 1
   OD
 OD;
 out # EXIT with: n P r OVER r P r #

);

basically C(n,r) = nCk = nPk/r! = n!/(n-r)!/r! #

CO does not prevent overflow! OP C = (CPREAL n, r)CPREAL: (

 IF n < r ORF r < 0 THEN IF NOT cp fix value error(CPARGS("C", ENTIER n,ENTIER r)) THEN stop FI FI;
 n P r / ( r P r )

); END CO

basically C(n,r) = nCk = nPk/r! = n!/(n-r)!/r! #

OP C = (CPREAL n, r)CPREAL: (

 IF n < r ORF r < 0 THEN IF NOT cp fix value error(("C",ENTIER n,ENTIER r)) THEN stop FI FI;
 CPREAL largest = ( r > n - r | r | n - r );
 CPREAL smallest = n - largest;
 CPREAL out := 1;
 REAL smaller fact := 2;
 REAL larger fact := largest+1;
 WHILE larger fact <= n DO # todo: check underslow here #

try and prevent overflow, p.s. there must be a smarter way to do this #

   out *:= larger fact;
   WHILE smaller fact <= smallest ANDF out > smaller fact DO 
     out /:= smaller fact;
     smaller fact +:= 1
   OD;
   larger fact +:= 1
 OD;
 out # EXIT with: n P r OVER r P r #

);

SKIP</lang>File: test_combinations_and_permutations.a68<lang algol68>#!/usr/bin/a68g --script #

-*- coding: utf-8 -*- #

CO REQUIRED by "prelude_combinations_and_permutations.a68" CO

 MODE CPINT = #LONG# INT;
 MODE CPOUT = #LONG# INT; # the answer, can be REAL #
 MODE CPREAL = REAL; # the answer, can be REAL #
 MODE CPARGS = STRUCT(CHAR name, #REF# CPINT n,k);
 PROC cp fix value error = (#REF# CPARGS args)BOOL: (
   putf(stand error, ($"Value error: "g(0)gg(0)"arg out of range"l$, 
                        n OF args, name OF args, k OF args)); 
   FALSE # unfixable #
 );

PR READ "prelude_combinations_and_permutations.a68" PR;

printf($"A sample of Permutations from 1 to 12:"l$); FOR i FROM 4 BY 1 TO 12 DO

 INT first = i - 2,
     second = i - ENTIER sqrt(i);
 printf(($g(0)" P "g(0)" = "g(0)$, i, first, i P first, $", "$));
 printf(($g(0)" P "g(0)" = "g(0)$, i, second, i P second, $l$))

OD;

printf($l"A sample of Combinations from 10 to 60:"l$); FOR i FROM 10 BY 10 TO 60 DO

 INT first = i - 2,
     second = i - ENTIER sqrt(i);
 printf(($"("g(0)" C "g(0)") = "g(0)$, i, first, i C first, $", "$));
 printf(($"("g(0)" C "g(0)") = "g(0)$, i, second, i C second, $l$))

OD;

printf($l"A sample of Permutations from 5 to 15000:"l$); FOR i FROM 5 BY 10 TO 150 DO

 REAL r = i,
      first = r - 2,
      second = r - ENTIER sqrt(r);
 printf(($g(0)" P "g(0)" = "g(-real width,real width-5,-1)$, r, first, r P first, $", "$));
 printf(($g(0)" P "g(0)" = "g(-real width,real width-5,-1)$, r, second, r P second, $l$))

OD;

printf($l"A sample of Combinations from 100 to 1000:"l$); FOR i FROM 100 BY 100 TO 1000 DO

 REAL r = i,
      first = r - 2,
      second = r - ENTIER sqrt(r);
 printf(($"("g(0)" C "g(0)") = "g(0,1)$, r, first, r C first, $", "$));
 printf(($"("g(0)" C "g(0)") = "g(0,1)$, r, second, r C second, $l$))

OD</lang>Output:

A sample of Permutations from 1 to 12:
4 P 2 = 12, 4 P 2 = 12
5 P 3 = 60, 5 P 3 = 60
6 P 4 = 360, 6 P 4 = 360
7 P 5 = 2520, 7 P 5 = 2520
8 P 6 = 20160, 8 P 6 = 20160
9 P 7 = 181440, 9 P 6 = 60480
10 P 8 = 1814400, 10 P 7 = 604800
11 P 9 = 19958400, 11 P 8 = 6652800
12 P 10 = 239500800, 12 P 9 = 79833600

A sample of Combinations from 10 to 60:
(10 C 8) = 45, (10 C 7) = 120
(20 C 18) = 190, (20 C 16) = 4845
(30 C 28) = 435, (30 C 25) = 142506
(40 C 38) = 780, (40 C 34) = 3838380
(50 C 48) = 1225, (50 C 43) = 99884400
(60 C 58) = 1770, (60 C 53) = 386206920

A sample of Permutations from 5 to 15000:
5 P 3 =  6.0000000000e1, 5 P 3 =  6.0000000000e1
15 P 13 =  6.538371840e11, 15 P 12 =  2.179457280e11
25 P 23 =  7.755605022e24, 25 P 20 =  1.292600837e23
35 P 33 =  5.166573983e39, 35 P 30 =  8.610956639e37
45 P 43 =  5.981111043e55, 45 P 39 =  1.661419734e53
55 P 53 =  6.348201677e72, 55 P 48 =  2.519127650e69
65 P 63 =  4.123825296e90, 65 P 57 =  2.045548262e86
75 P 73 =  1.24045704e109, 75 P 67 =  6.15306072e104
85 P 83 =  1.40855206e128, 85 P 76 =  7.76318374e122
95 P 93 =  5.16498924e147, 95 P 86 =  2.84666515e142
105 P 103 =  5.40698379e167, 105 P 95 =  2.98003957e161
115 P 113 =  1.46254685e188, 115 P 105 =  8.06077407e181
125 P 123 =  9.41338588e208, 125 P 114 =  4.71650327e201
135 P 133 =  1.34523635e230, 135 P 124 =  6.74020139e222
145 P 143 =  4.02396303e251, 145 P 133 =  1.68014597e243

A sample of Combinations from 100 to 1000:
(100 C 98) = 4950.0, (100 C 90) = 17310309456440.0
(200 C 198) = 19900.0, (200 C 186) = 1179791641436990000000.0
(300 C 298) = 44850.0, (300 C 283) = 2287708142023200000000000000.0
(400 C 398) = 79800.0, (400 C 380) = 2788360983670890000000000000000000.0
(500 C 498) = 124750.0, (500 C 478) = 132736424690819000000000000000000000000.0
(600 C 598) = 179700.0, (600 C 576) = 4791686682466570000000000000000000000000000.0
(700 C 698) = 244650.0, (700 C 674) = 145478651313634000000000000000000000000000000000.0
(800 C 798) = 319600.0, (800 C 772) = 3933526871034580000000000000000000000000000000000000.0
(900 C 898) = 404550.0, (900 C 870) = 98033481673745800000000000000000000000000000000000000000.0
(1000 C 998) = 499500.0, (1000 C 969) = 76023224077694500000000000000000000000000000000000000000000.0