n_choose_r.cpp

Go to the documentation of this file.

 
#include <cassert>   
#include <cstdint>
#include <iostream>  
namespace math {
template <class T>
T n_choose_r(T n, T r) {
    if (r > n / 2) {
        r = n - r;  // Because of the fact that  nCr(n, r) == nCr(n, n - r)
    }
    T ans = 1;
    for (int i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }
    return ans;
}
}  // namespace math
 
static void test() {
    // First test on 5 choose 2
    uint8_t t = math::n_choose_r(5, 2);
    assert(((void)"10 is the answer but function says otherwise.\n", t == 10));
    std::cout << "First test passes." << std::endl;
    // Second test on 5 choose 3
    t = math::n_choose_r(5, 3);
    assert(
        ((void)"10 is the answer but the function says otherwise.\n", t == 10));
    std::cout << "Second test passes." << std::endl;
    // Third test on 3 choose 2
    t = math::n_choose_r(3, 2);
    assert(
        ((void)"3 is the answer but the function says otherwise.\n", t == 3));
    std::cout << "Third test passes." << std::endl;
    // Fourth test on 10 choose 4
    t = math::n_choose_r(10, 4);
    assert(((void)"210 is the answer but the function says otherwise.\n",
            t == 210));
    std::cout << "Fourth test passes." << std::endl;
}
 
int main(int argc, char *argv[]) {
    test();  // executing tests
    return 0;
}