Compute Combinations (nCr) in C

Introduction

In this lab, you will learn how to compute combinations (nCr) using a C program. The lab covers two main steps: reading the input values for n and r, and then implementing the formula to calculate the combination nCr = n! / (r! * (n-r)!). By the end of this lab, you will have a working C program that can compute combinations for any given values of n and r.

The lab starts by demonstrating how to read the input values for n and r using the scanf() function. It then introduces the implementation of factorial and combination calculation functions, which are used to compute the final result. The lab provides the complete code and step-by-step instructions, making it easy for you to follow along and apply the concepts in your own projects.

Skills Graph

Read n and r

In this step, you will learn how to read input values for n and r to compute combinations in a C program.

First, create a new C file for your combination calculation program:

cd ~/project
nano combinations.c

Now, add the following code to read input values:

#include <stdio.h>

int main() {
    int n, r;

    // Prompt user to enter values for n and r
    printf("Enter the value of n: ");
    scanf("%d", &n);

    printf("Enter the value of r: ");
    scanf("%d", &r);

    // Print the entered values to verify input
    printf("You entered n = %d and r = %d\n", n, r);

    return 0;
}

Compile and run the program to test input:

gcc combinations.c -o combinations
./combinations

Example output:

Enter the value of n: 5
Enter the value of r: 3
You entered n = 5 and r = 3

This code demonstrates how to:

• Use scanf() to read integer inputs from the user
• Prompt the user to enter values for n and r
• Print the entered values to confirm correct input

The code sets up the foundation for computing combinations by first capturing the necessary input values n and r.

Compute nCr = n!/(r!(n-r)!)

In this step, you will implement a function to calculate the factorial and compute combinations using the formula nCr = n! / (r! * (n-r)!).

Open the previous combinations.c file and update it with the factorial and combination calculation functions:

cd ~/project
nano combinations.c

Add the following code to implement factorial and combination calculations:

#include <stdio.h>

// Function to calculate factorial
unsigned long long factorial(int num) {
    if (num == 0 || num == 1) {
        return 1;
    }

    unsigned long long result = 1;
    for (int i = 2; i <= num; i++) {
        result *= i;
    }

    return result;
}

// Function to calculate combinations (nCr)
unsigned long long combinations(int n, int r) {
    // Validate input
    if (r > n) {
        return 0;
    }

    // Use the combination formula: nCr = n! / (r! * (n-r)!)
    unsigned long long numerator = factorial(n);
    unsigned long long denominator = factorial(r) * factorial(n - r);

    return numerator / denominator;
}

int main() {
    int n, r;

    // Prompt user to enter values for n and r
    printf("Enter the value of n: ");
    scanf("%d", &n);

    printf("Enter the value of r: ");
    scanf("%d", &r);

    // Calculate and print the combination
    unsigned long long result = combinations(n, r);

    printf("Combination C(%d, %d) = %llu\n", n, r, result);

    return 0;
}

Compile and run the program:

gcc combinations.c -o combinations
./combinations

Example output:

Enter the value of n: 5
Enter the value of r: 3
Combination C(5, 3) = 10

Key points in this implementation:

• factorial() function calculates the factorial of a given number
• combinations() function implements the combination formula
• Uses unsigned long long to handle larger factorial calculations
• Validates input to prevent invalid combinations

Print the Result

In this step, you will enhance the combination calculation program by adding more informative output and error handling.

Open the combinations.c file and modify the code:

cd ~/project
nano combinations.c

Update the code with improved result printing and input validation:

#include <stdio.h>

// Previous factorial and combinations functions remain the same

int main() {
    int n, r;

    // Prompt user to enter values for n and r
    printf("Combination (nCr) Calculator\n");
    printf("----------------------------\n");

    // Input validation
    do {
        printf("Enter the total number of items (n): ");
        scanf("%d", &n);

        if (n < 0) {
            printf("Error: n must be a non-negative integer.\n");
        }
    } while (n < 0);

    do {
        printf("Enter the number of items to choose (r): ");
        scanf("%d", &r);

        if (r < 0 || r > n) {
            printf("Error: r must be between 0 and n.\n");
        }
    } while (r < 0 || r > n);

    // Calculate combination
    unsigned long long result = combinations(n, r);

    // Detailed result output
    printf("\nResult Breakdown:\n");
    printf("----------------\n");
    printf("Total items (n): %d\n", n);
    printf("Items to choose (r): %d\n", r);
    printf("Possible combinations (nCr): %llu\n", result);

    // Explanation of the result
    printf("\nInterpretation:\n");
    printf("---------------\n");
    printf("There are %llu ways to choose %d items from a set of %d items.\n",
           result, r, n);

    return 0;
}

Compile and run the program:

gcc combinations.c -o combinations
./combinations

Example output:

Combination (nCr) Calculator
----------------------------
Enter the total number of items (n): 5
Enter the number of items to choose (r): 3

Result Breakdown:
----------------
Total items (n): 5
Items to choose (r): 3
Possible combinations (nCr): 10

Interpretation:
---------------
There are 10 ways to choose 3 items from a set of 5 items.

Key improvements:

• Added input validation to prevent invalid inputs
• Enhanced output with detailed result breakdown
• Provided interpretation of the combination result

Summary

In this lab, you learned how to read input values for n and r, and then compute the combinations (nCr) using the formula nCr = n! / (r! * (n-r)!). You implemented functions to calculate the factorial and the combinations, and then used these functions to compute the final result. The key steps were: 1) reading the input values for n and r, and 2) computing the combinations using the formula and the factorial function.