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

问题:

Here I try to write a program in C++ to find NCR. But I've got a problem in the result. It is not correct. Can you help me find what the mistake is in the 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 A Digit for n";
    cin>>n;
    int r;
         //cout<<"Enter A Digit for r";
    cin>>r;
    int result=NCR(n,r);
    cout<<result;
    return 0;
}

回答1:

Your formula is totally wrong, it's supposed to be fact(n)/fact(r)/fact(n-r), but that is in turn a very inefficient way to compute it.

See Fast computation of multi-category number of combinations and especially my comments on that question. (Oh, and please reopen that question also so I can answer it properly)

The single-split case is actually very easy to 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 i = 2; i <= k; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}

Demo: http://ideone.com/aDJXNO

If the result doesn't fit, you can calculate the sum of logarithms and get the number of combinations inexactly as a double. Or use an arbitrary-precision integer library.

---

I'm putting my solution to the other, closely related question here, because ideone.com has been losing code snippets lately, and the other question is still closed to 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 i = 1; i <= 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 i = 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 i = largest + 1; i <= 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 i = 0; i < powers.size(); ++i ) {
        if (powers[i]) {
            std::cout << sep << i;
            sep = " * ";
            if (powers[i] > 1)
                std::cout << "**" << powers[i];
        }
    }
    std::cout << "\n\n";
}

回答2:

The definition of N choose R is to compute the two products and divide one with the other,

(N * N-1 * N-2 * ... * N-R+1) / (1 * 2 * 3 * ... * R)

However, the multiplications may become too large really quick and overflow existing data type. The implementation trick is to reorder the multiplication and divisions as,

(N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-R+1)/R

It's guaranteed that at each step the results is divisible (for n continuous numbers, one of them must be divisible by n, so is the product of these numbers).

For example, for N choose 3, at least one of the N, N-1, N-2 will be a multiple of 3, and for N choose 4, at least one of N, N-1, N-2, N-3 will be a multiple of 4.

C++ code given below.

int NCR(int n, int r)
{
    if (r == 0) return 1;

    /*
     Extra computation saving for large R,
     using property:
     N choose R = N choose (N-R)
    */
    if (r > n / 2) return NCR(n, n - r); 

    long res = 1; 

    for (int k = 1; k <= r; ++k)
    {
        res *= n - k + 1;
        res /= k;
    }

    return res;
}

回答3:

A nice way to implement n-choose-k is to base it not on factorial, but on a "rising product" function which is closely related to the factorial.

The rising_product(m, n) multiplies together m * (m + 1) * (m + 2) * ... * n, with rules for handling various corner cases, like n >= m, or n <= 1:

See here for an implementation nCk as well as nPk as a intrinsic functions in an interpreted programming language written in C:

static val rising_product(val m, val n)
{
  val acc;

  if (lt(n, one))
    return one;

  if (ge(m, n))
    return one;

  if (lt(m, one))
    m = one;

  acc = m;

  m = plus(m, one);

  while (le(m, n)) {
    acc = mul(acc, m);
    m = plus(m, one);
  }

  return acc;
}

val n_choose_k(val n, val k)
{
  val top = rising_product(plus(minus(n, k), one), n);
  val bottom = rising_product(one, k);
  return trunc(top, bottom);
}

val n_perm_k(val n, val k)
{
  return rising_product(plus(minus(n, k), one), n);
}

This code doesn't use operators like + and < because it is type generic (the type val represents a value of any kinds, such as various kinds of numbers including "bignum" integers) and because it is written in C (no overloading), and because it is the basis for a Lisp-like language that doesn't have infix syntax.

In spite of that, this n-choose-k implementation has a simple structure that is easy to follow.

Legend: le: less than or equal; ge: greater than or equal; trunc: truncating division; plus: addition, mul: multiplication, one: a val typed constant for the number one.

回答4:

the line

else return (n*fact(n-1))/fact(n-1)*fact(n-r);

should be

else return (n*fact(n-1))/(fact(r)*fact(n-r));

or even

else return fact(n)/(fact(r)*fact(n-r));

回答5:

Use double instead of int.

UPDATE:

Your formula is also wrong. You should use fact(n)/fact(r)/fact(n-r)

回答6:

this is for reference to not to get time limit exceeded while solving nCr in competitive programming,i am posting this as it will be helpful to u as you already got answer for ur question, Getting the prime factorization of the binomial coefficient is probably the most efficient way to calculate it, especially if multiplication is expensive. This is certainly true of the related problem of calculating factorial (see Click here for example).

Here is a simple algorithm based on the Sieve of Eratosthenes that calculates the prime factorization. The idea is basically to go through the primes as you find them using the sieve, but then also to calculate how many of their multiples fall in the ranges [1, k] and [n-k+1,n]. The Sieve is essentially an O(n \log \log n) algorithm, but there is no multiplication done. The actual number of multiplications necessary once the prime factorization is found is at worst O\left(\frac{n \log \log n}{\log n}\right) and there are probably faster ways than that.

prime_factors = []

n = 20
k = 10

composite = [True] * 2 + [False] * n

for p in xrange(n + 1):
if composite[p]:
    continue

q = p
m = 1
total_prime_power = 0
prime_power = [0] * (n + 1)

while True:

    prime_power[q] = prime_power[m] + 1
    r = q

    if q <= k:
        total_prime_power -= prime_power[q]

    if q > n - k:
        total_prime_power += prime_power[q]

    m += 1
    q += p

    if q > n:
        break

    composite[q] = True

prime_factors.append([p, total_prime_power])

 print prime_factors

回答7:

Recursive function is used incorrectly here. fact() function should be changed into this:

int fact(int n){
if(n==0||n==1) //factorial of both 0 and 1 is 1. Base case.
{
    return 1;
}else

    return (n*fact(n-1));//recursive call.

};

Recursive call should be made in else part.

NCR() function should be changed into this:

int NCR(int n,int r){
    if(n==r) {
        return 1;
    } else if (r==0&&n!=0) {
        return 1;
    } else if(r==1)
    {
        return n;
    }
    else
    {
        return fact(n)/(fact(r)*fact(n-r));
    }
};