des.math.combin source code

1 module des.math.combin;
2 
3 /// factorial
4 long fact( long a ) pure nothrow
5 in { assert( a >= 0 ); }
6 out(res) { assert( res >= 0 ); }
7 body
8 {
9     if( a <= 2 ) return a;
10     return a * fact(a-1);
11 }
12 
13 unittest
14 {
15     assert( fact(0) == 0 );
16     assert( fact(1) == 1 );
17     assert( fact(2) == 2 );
18     assert( fact(3) == 6 );
19     assert( fact(4) == 24 );
20     assert( fact(5) == 120 );
21 }
22 
23 /// equals to fact(n) / ( fact(k) * fact( n-k ) )
24 long combination( long n, long k ) pure nothrow
25 in
26 {
27     assert( k > 0 );
28     assert( n >= 0 );
29 }
30 out(res) { assert( res >= 0 ); }
31 body
32 {
33     if( k == 1 || k == n-1 ) return n;
34     long a = n * (n-1);
35     long b = k;
36 
37     foreach( i; 2 .. k )
38     {
39         a *= (n-i);
40         b *= i;
41     }
42 
43     return a / b;
44 }
45 
46 unittest
47 {
48     static pure nothrow long comb2( long n, long k )
49     { return fact(n) / ( fact(k) * fact( n-k ) ); }
50 
51     foreach( k; 1 .. 10 )
52         assert( combination(10,k) == comb2(10,k) );
53 }
54 
55 /// equals to fact(n) / fact(n-k)
56 pure nothrow long partial_permutation( long n, long k )
57 in
58 {
59     assert( k > 0 );
60     assert( n >= k );
61 }
62 out(res) { assert( res >= 0 ); }
63 body
64 {
65     if( k == 1 ) return n;
66 
67     long res = n * (n-1);
68 
69     foreach( i; 2 .. k )
70         res *= (n-i);
71 
72     return res;
73 }
74 
75 unittest
76 {
77     static pure nothrow long perm2( long n, long k )
78     { return fact(n) / fact( n-k ); }
79 
80     foreach( k; 1 .. 10 )
81         assert( partial_permutation(10,k) == perm2(10,k) );
82 }