1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
/*
** Compute C(n,m) = the number of combinations of n items,
** taken m at a time.
**
** Written by Thad Smith III, Boulder County, CO.
** Released to the Public Domain 10/14/91.
**
** The def of this function is
** C(n,m) = n! / (m! * (n-m)!).
** Computing this formula can cause overflow for large values of n,
** even when C(n,m) would be defined.
**
** The first version will not overflow if C(n,m) * (n-m+1) < ULONG_MAX.
** The second version will not overflow if C(n,m) < ULONG_MAX, but
** is slightly more complex.
** Function domain: n >= 0, 0 <= m <= n.
**
** Both versions work by reducing the product as it is computed. It
** relies on the property that the product on n consecutive integers
** must be evenly divisible by n.
**
** The first version can be changed to make cnm and the return value
** double to extend the range of the function.
*/
unsigned long ncomb1 (int n, int m)
{
unsigned long cnm = 1UL;
int i;
if (m*2 >n) m = n-m;
for (i=1 ; i <= m; n--, i++)
cnm = cnm * n / i;
return cnm;
}
unsigned long ncomb2 (int n, int m)
{
unsigned long cnm = 1UL;
int i, f;
if (m*2 >n) m = n-m;
for (i=1 ; i <= m; n--, i++)
{
if ((f=n) % i == 0)
f /= i;
else cnm /= i;
cnm *= f;
}
return cnm;
}
#ifdef TEST
#include <stdio.h>
#include <stdlib.h>
main (int argc, char *argv[]) {
int n,m;
n = atoi (argv[1]);
m = atoi (argv[2]);
printf ("ncomb1 = %lu, ncomb2 = %lu\n", ncomb1(n,m), ncomb2(n,m));
return 0;
}
#endif
|
