Permutations and Combinations in Data Structures and Algorithms with JavaScript

In the realm of Data Structures and Algorithms (DSA), permutations and combinations play a crucial role. They are fundamental concepts in combinatorics and have wide-ranging applications in computer science, particularly in DSA.

Permutations

A permutation is an arrangement of all the members of a set into some sequence or order. The number of permutations on a set of n elements is given by n! (n factorial).

Here’s a simple JavaScript function to calculate n!:

JavaScript

function factorial(n) {
    if (n === 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

Combinations

A combination is a selection of items from a larger set, where the order of selection does not matter. The number of combinations of n items taken r at a time is given by nCr = n! / r!(n-r)!.

Here’s a JavaScript function to calculate nCr:

JavaScript

function combination(n, r) {
    return factorial(n) / (factorial(r) * factorial(n - r));
}

Top 5 Algorithms for Implementing Permutations and Combinations

1. Generating All Permutations

Here’s a simple recursive algorithm to generate all permutations of a given string:

JavaScript

function permute(str, l, r) {
    if (l == r)
        console.log(str);
    else {
        for (let i = l; i <= r; i++) {
            str = swap(str, l, i);
            permute(str, l + 1, r);
            str = swap(str, l, i); // backtrack
        }
    }
}

function swap(str, i, j) {
    let charArray = str.split('');
    let temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return charArray.join('');
}

2. Generating All Combinations

Here’s a simple recursive algorithm to generate all combinations of a given string:

JavaScript

function combine(str, start, end, output) {
    for (let i = start; i <= end; i++) {
        output += str[i];
        console.log(output);
        if (i < str.length - 1) {
            combine(str, i + 1, end, output);
        }
        output = output.slice(0, output.length - 1);
    }
}

3. Heap’s Algorithm for Generating Permutations

Heap’s algorithm generates all possible permutations of n objects. It minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements.

JavaScript

function heapPermutation(a, size, n) {
    if (size == 1) {
        console.log(a.join(''));
        return;
    }
 
    for (let i = 0; i < size; i++) {
        heapPermutation(a, size - 1, n);
        if (size % 2 == 1) {
            let temp = a[0];
            a[0] = a[size - 1];
            a[size - 1] = temp;
        } else {
            let temp = a[i];
            a[i] = a[size - 1];
            a[size - 1] = temp;
        }
    }
}

4. Lexicographically Sorted Permutations

This algorithm generates permutations in lexicographically sorted order.

JavaScript

function sortedPermutations(str) {
    let chars = str.split('').sort();
    while (true) {
        console.log(chars.join(''));
        let i = chars.length - 2;
        while (i >= 0 && chars[i] >= chars[i + 1]) {
            i--;
        }
        if (i < 0) {
            break;
        }
        let j = chars.length - 1;
        while (chars[j] <= chars[i]) {
            j--;
        }
        [chars[i], chars[j]] = [chars[j], chars[i]]; // swap
        chars = chars.slice(0, i + 1).concat(chars.slice(i + 1).reverse());
    }
}

5. Combinations using Backtracking

This algorithm generates all combinations of a string using backtracking.

JavaScript

function combinations(str, index, data, i) {
    if (index == i) {
        console.log(data.join(''));
        return;
    }
    if (i >= str.length)
        return;
    data[index] = str[i];
    combinations(str, index + 1, data, i + 1);
    combinations(str, index, data, i + 1);
}

These are just a few examples of how permutations and combinations can be implemented in JavaScript. They are fundamental concepts in DSA and understanding them can help solve complex problems more efficiently.