des.math.combin.count source code

1 module des.math.combin.count;
2 
3 import des.ts;
4 
5 version(unittest) import std..string : format;
6 
7 /// factorial
8 long fact( long n ) pure nothrow
9 in { assert( n >= 0 ); }
10 out(res) { assert( res >= 0 ); }
11 body
12 {
13     if( n <= 2 ) return n;
14     long res = 1;
15     foreach( i; 2 .. n+1 ) res *= i;
16     return res;
17 }
18 
19 unittest
20 {
21     assertEq( fact(0), 0 );
22     assertEq( fact(1), 1 );
23     assertEq( fact(2), 2 );
24     assertEq( fact(3), 6 );
25     assertEq( fact(4), 24 );
26     assertEq( fact(5), 120 );
27     assertEq( fact(6), 720 );
28     assertEq( fact(7), 5040 );
29     assertEq( fact(8), 40320 );
30     assertEq( fact(9), 362880 );
31     assertEq( fact(10), 3628800 );
32 }
33 
34 /// equals to fact(n) / ( fact(k) * fact( n-k ) )
35 long combinationCount( long n, long k ) pure nothrow
36 in
37 {
38     assert( k > 0 );
39     assert( n >= 0 );
40 }
41 out(res) { assert( res >= 0 ); }
42 body
43 {
44     if( k == 1 || k == n-1 ) return n;
45     long a = n * (n-1);
46     long b = k;
47 
48     foreach( i; 2 .. k )
49     {
50         a *= (n-i);
51         b *= i;
52     }
53 
54     return a / b;
55 }
56 
57 unittest
58 {
59     static pure nothrow long comb2( long n, long k )
60     { return fact(n) / ( fact(k) * fact( n-k ) ); }
61 
62     foreach( k; 1 .. 10 )
63         assertEq( combinationCount(10,k), comb2(10,k),
64                   format( "equal test fails with k==%d, %%s != %%s", k ) );
65 }
66 
67 /// equals to fact(n) / fact(n-k)
68 long partialPermutationCount( long n, long k ) pure nothrow
69 in
70 {
71     assert( k > 0 );
72     assert( n >= k );
73 }
74 out(res) { assert( res >= 0 ); }
75 body
76 {
77     if( k == 1 ) return n;
78 
79     long res = n * (n-1);
80 
81     foreach( i; 2 .. k )
82         res *= (n-i);
83 
84     return res;
85 }
86 
87 unittest
88 {
89     static pure nothrow long perm2( long n, long k )
90     { return fact(n) / fact( n-k ); }
91 
92     foreach( k; 1 .. 10 )
93         assertEq( partialPermutationCount(10,k), perm2(10,k),
94                   format( "equal test fails with k==%d, %%s != %%s", k ) );
95 }