home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / COMBIN.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  2KB  |  78 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /*
  4. ** Compute C(n,m) = the number of combinations of n items,
  5. ** taken m at a time.
  6. **
  7. ** Written by Thad Smith III, Boulder County, CO.
  8. ** Released to the Public Domain  10/14/91.
  9. **
  10. ** The def of this function is
  11. **      C(n,m)  = n! / (m! * (n-m)!).
  12. ** Computing this formula can cause overflow for large values of n,
  13. ** even when C(n,m) would be defined.
  14. **
  15. ** The first version will not overflow if C(n,m) * (n-m+1) < ULONG_MAX.
  16. ** The second version will not overflow if C(n,m) < ULONG_MAX, but
  17. ** is slightly more complex.
  18. ** Function domain: n >= 0,  0 <= m <= n.
  19. **
  20. ** Both versions work by reducing the product as it is computed.  It
  21. ** relies on the property that the product on n consecutive integers
  22. ** must be evenly divisible by n.
  23. **
  24. ** The first version can be changed to make cnm and the return value
  25. ** double to extend the range of the function.
  26. */
  27.  
  28. #include "snipmath.h"
  29.  
  30. DWORD ncomb1 (int n, int m)
  31. {
  32.       DWORD cnm = 1UL;
  33.       int i;
  34.  
  35.       if (m*2 >n) m = n-m;
  36.       for (i=1 ; i <= m; n--, i++)
  37.             cnm = cnm * n / i;
  38.       return cnm;
  39. }
  40.  
  41. DWORD ncomb2 (int n, int m)
  42. {
  43.       DWORD cnm = 1UL;
  44.       int i, f;
  45.  
  46.       if (m*2 >n) m = n-m;
  47.       for (i=1 ; i <= m; n--, i++)
  48.       {
  49.             if ((f=n) % i == 0)
  50.                   f   /= i;
  51.             else  cnm /= i;
  52.             cnm *= f;
  53.       }
  54.       return cnm;
  55. }
  56.  
  57. #ifdef TEST
  58.  
  59. #include <stdio.h>
  60. #include <stdlib.h>
  61.  
  62. #ifdef __WATCOMC__
  63.  #pragma off (unreferenced);
  64. #endif
  65. #ifdef __TURBOC__
  66.  #pragma argsused
  67. #endif
  68.  
  69. main (int argc, char *argv[]) {
  70.     int n,m;
  71.     n = atoi (argv[1]);
  72.     m = atoi (argv[2]);
  73.     printf ("ncomb1 = %lu, ncomb2 = %lu\n", ncomb1(n,m), ncomb2(n,m));
  74.     return 0;
  75. }
  76.  
  77. #endif /* TEST */
  78.