git.ozlabs.org Git - ccan/blob - junkcode/tterribe@email.unc.edu-nmbrthry/choose.c

   1 #include "choose.h"
   2 #include "gcd.h"
   3
   4 /*Computes the number of combinations of _n items, taken _m at a time without
   5    overflow.
   6   _n: The total number of items.
   7   _m: The number taken at a time.
   8   Return: The number of combinations of _n items taken _m at a time.*/
   9 unsigned choose(int _n,int _m){
  10   unsigned ret;
  11   int      i;
  12   ret=1;
  13   for(i=1;i<=_m;_n--,i++){
  14     int nmi;
  15     nmi=_n%i;
  16     if(nmi==0)ret*=_n/i;
  17     else if(ret%i==0)ret=(ret/i)*_n;
  18     else{
  19       int d;
  20       d=gcd(i,nmi);
  21       ret=(ret/(i/d))*(_n/d);
  22     }
  23   }
  24   return ret;
  25 }