Calculate N Choose R in C++

What is n choose r?

The notation "n choose r" represents the number of combinations of n items taken r at a time. It's calculated using the combination formula:

This formula gives the number of ways to choose r items from n items without considering the order of selection. For example, if you have 5 cards and want to choose 2, there are 10 possible combinations (5 choose 2 = 10).

How to calculate n choose r in C++

Implementing the combination formula in C++ requires calculating factorials and handling large numbers. Here's a complete implementation:

#include <iostream>
#include <vector>

using namespace std;

// Function to calculate factorial
long long factorial(int n) {
    if (n == 0 || n == 1) return 1;
    long long result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// Function to calculate n choose r
long long nChooseR(int n, int r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    return factorial(n) / (factorial(r) * factorial(n - r));
}

int main() {
    int n, r;
    cout << "Enter n and r: ";
    cin >> n >> r;
    cout << n << " choose " << r << " = " << nChooseR(n, r) << endl;
    return 0;
}

Optimized Implementation

For larger values of n and r, the factorial approach can lead to integer overflow. A more efficient method uses multiplicative formula:

long long nChooseROptimized(int n, int r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;

    r = min(r, n - r); // Take advantage of symmetry
    long long result = 1;

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

    return result;
}

Handling Large Numbers

For very large combinations, you might need to use arbitrary-precision arithmetic libraries like GMP (GNU Multiple Precision Arithmetic Library).

Example calculation

Let's calculate 5 choose 2 using both methods:

Both methods correctly calculate that there are 10 ways to choose 2 items from 5.

Common applications

The combination formula finds applications in various fields:

• Probability: Calculating probabilities in lotteries, card games, and other random selection scenarios
• Statistics: Designing experiments and analyzing data
• Computer Science: Algorithms for generating permutations and combinations
• Combinatorics: Counting problems in discrete mathematics
• Physics: Quantum state calculations and particle interactions