How to calculate combination in JavaScript?

Calculating combinations in JavaScript can refer to two main scenarios: determining the number of possible combinations (often denoted as C(n, k) or "n choose k") or generating all possible combinations (subsets or subsequences) from a given set of elements. Both can be effectively handled in JavaScript.

Understanding Combinations

A combination is a selection of items from a larger set where the order of selection does not matter. For example, if you choose two fruits from apples, bananas, and cherries, picking (apple, banana) is the same as (banana, apple). This distinguishes combinations from permutations, where the order does matter.

Method 1: Calculating the Number of Combinations (nCr)

To calculate the number of combinations, we use the mathematical formula for "n choose k," which is:

$C(n, k) = \frac{n!}{k! * (n-k)!}$

Where:

• n is the total number of items available.
• k is the number of items to choose.
• ! denotes the factorial operation (e.g., 5! = 5 4 3 2 1).

Implementing the Factorial Function

First, we need a helper function to calculate the factorial of a number.

/**
 * Calculates the factorial of a non-negative integer.
 * @param {number} num The number to calculate the factorial for.
 * @returns {number} The factorial of the number.
 */
function factorial(num) {
    if (num < 0) {
        return NaN; // Factorial not defined for negative numbers
    }
    if (num === 0 || num === 1) {
        return 1;
    }
    let result = 1;
    for (let i = 2; i <= num; i++) {
        result *= i;
    }
    return result;
}

Implementing the Combination Function (nCr)

Using the factorial function, we can now implement the combinationsNcr function:

/**
 * Calculates the number of combinations (n choose k).
 * @param {number} n The total number of items.
 * @param {number} k The number of items to choose.
 * @returns {number} The number of combinations, or 0 if n < k or k < 0.
 */
function combinationsNcr(n, k) {
    if (k < 0 || k > n) {
        return 0; // Invalid input for combinations
    }
    if (k === 0 || k === n) {
        return 1; // Base cases: choosing 0 or all items results in 1 combination
    }
    if (k > n / 2) {
        k = n - k; // Optimization: C(n, k) = C(n, n-k)
    }

    // Using the factorial function
    return factorial(n) / (factorial(k) * factorial(n - k));
}

Example Usage:

console.log(combinationsNcr(5, 2)); // Output: 10 (e.g., choosing 2 items from 5)
console.log(combinationsNcr(4, 3)); // Output: 4 (e.g., choosing 3 items from 4)
console.log(combinationsNcr(10, 0)); // Output: 1
console.log(combinationsNcr(7, 7)); // Output: 1

Method 2: Generating All Combinations (Subsets/Subsequences)

Generating all combinations means creating every possible unique selection of elements from a given set (e.g., string characters or array elements). This is often achieved using recursive algorithms or iterative methods.

Recursive Approach for Strings or Arrays

A common and intuitive way to generate all combinations (subsequences or subsets) is through recursion. The core idea is that for each element in the input set, you have two choices: include it in the current combination or exclude it.

Let's illustrate with a string. We'll build combinations by traversing the string character by character.

Core Recursive Logic:

1. Base Case: If you've processed all characters in the input string (i.e., the index reaches the string.length), then the current accumulated string represents a complete combination (subsequence). This combination is then typically stored or outputted. For instance, a function structure often includes a base case like:

   if (index === str.length) {
       console.log(current); // Output each combination.
       return;
   }

2. Recursive Step (Include): You decide to include the character at the current index. You append this character to your current combination and make a recursive call to process the next character. This path progressively adds characters to form a combination. A common implementation of this "include" step is:

   // Include the character at the current index.
   combinationsRecursive(str, index + 1, current + str[index]);

   This specifically takes str[index] and appends it to current, then moves to index + 1. This iterative inclusion of characters is a fundamental component of many combinatorial algorithms.

3. Recursive Step (Exclude): To generate all possible combinations (subsequences), you must also consider the path where you exclude the character at the current index. You make a recursive call to process the next character without adding the current character to your current combination.

By combining both the "include" and "exclude" paths, the recursion explores all possible selections.

Complete Recursive Function Example for Strings:

/**
 * Generates and logs all possible combinations (subsequences) of a string.
 * @param {string} str The input string.
 * @param {number} index The current index being processed (starts at 0).
 * @param {string} current The current combination built so far (starts as '').
 * @param {Array<string>} result An array to store all generated combinations.
 */
function generateStringCombinations(str, index = 0, current = '', result = []) {
    // Base Case: If the end of the string is reached, a combination is formed.
    if (index === str.length) {
        result.push(current); // Store the combination
        return;
    }

    // Recursive Step 1: Include the character at the current index.
    // This part demonstrates the progressive inclusion seen in some patterns:
    // combinationsRecursive(str, index + 1, current + str[index]);
    generateStringCombinations(str, index + 1, current + str[index], result);

    // Recursive Step 2: Exclude the character at the current index.
    // This call ensures all non-contiguous combinations are also generated.
    generateStringCombinations(str, index + 1, current, result);
}

Example Usage:

let allCombinations = [];
generateStringCombinations("abc", 0, '', allCombinations);

console.log("Combinations of 'abc':");
// Note: This will include the empty string as a combination
allCombinations.sort().forEach(c => console.log(`'${c}'`));

/* Expected Output (order might vary, but includes all 2^n subsequences):
Combinations of 'abc':
''
'a'
'ab'
'abc'
'ac'
'b'
'bc'
'c'
*/

This method generates all $2^n$ subsequences, including the empty string. If you need combinations of a specific length, you would add a condition in the base case to check current.length.

Table: Comparison of Combination Types