combinatorics - Number of combinations (N choose R) in C++ -

here try write program in c++ find ncr. i've got problem in result. not correct. can me find mistake in program?

#include <iostream> using namespace std; int fact(int n){     if(n==0) return 1;     if (n>0) return n*fact(n-1); };  int ncr(int n,int r){     if(n==r) return 1;     if (r==0&&n!=0) return 1;     else return (n*fact(n-1))/fact(n-1)*fact(n-r); };  int main(){     int n;  //cout<<"enter digit n";     cin>>n;     int r;          //cout<<"enter digit r";     cin>>r;     int result=ncr(n,r);     cout<<result;     return 0; } 

your formula totally wrong, it's supposed fact(n)/fact(r)/fact(n-r), in turn inefficient way compute it.

see fast computation of multi-category number of combinations , comments on question. (oh, , please reopen question can answer properly)

the single-split case easy handle:

unsigned nchoosek( unsigned n, unsigned k ) {     if (k > n) return 0;     if (k * 2 > n) k = n-k;     if (k == 0) return 1;      int result = n;     for( int = 2; <= k; ++i ) {         result *= (n-i+1);         result /= i;     }     return result; } 

demo: http://ideone.com/adjxno

if result doesn't fit, can calculate sum of logarithms , number of combinations inexactly double. or use arbitrary-precision integer library.

---

i'm putting solution other, closely related question here, because ideone.com has been losing code snippets lately, , other question still closed new answers.

#include <utility> #include <vector>  std::vector< std::pair<int, int> > factor_table; void fill_sieve( int n ) {     factor_table.resize(n+1);     for( int = 1; <= n; ++i )         factor_table[i] = std::pair<int, int>(i, 1);     for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {         if (factor_table[j].second == 1) {             int = j;             int ij = j2;             while (ij <= n) {                 factor_table[ij] = std::pair<int, int>(j, i);                 ++i;                 ij += j;             }         }     } }  std::vector<unsigned> powers;  template<int dir> void factor( int num ) {     while (num != 1) {         powers[factor_table[num].first] += dir;         num = factor_table[num].second;     } }  template<unsigned n> void calc_combinations(unsigned (&bin_sizes)[n]) {     using std::swap;      powers.resize(0);     if (n < 2) return;      unsigned& largest = bin_sizes[0];     size_t sum = largest;     for( int bin = 1; bin < n; ++bin ) {         unsigned& this_bin = bin_sizes[bin];         sum += this_bin;         if (this_bin > largest) swap(this_bin, largest);     }     fill_sieve(sum);      powers.resize(sum+1);     for( unsigned = largest + 1; <= sum; ++i ) factor<+1>(i);     for( unsigned bin = 1; bin < n; ++bin )         for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j); }  #include <iostream> #include <cmath> int main(void) {     unsigned bin_sizes[] = { 8, 1, 18, 19, 10, 10, 7, 18, 7, 2, 16, 8, 5, 8, 2, 3, 19, 19, 12, 1, 5, 7, 16, 0, 1, 3, 13, 15, 13, 9, 11, 6, 15, 4, 14, 4, 7, 13, 16, 2, 19, 16, 10, 9, 9, 6, 10, 10, 16, 16 };     calc_combinations(bin_sizes);     char* sep = "";     for( unsigned = 0; < powers.size(); ++i ) {         if (powers[i]) {             std::cout << sep << i;             sep = " * ";             if (powers[i] > 1)                 std::cout << "**" << powers[i];         }     }     std::cout << "\n\n"; }