des.math.combin source code

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