In a previous post, I discussed an algorithm to generate permutations using Typescript. Today I will show a similar idea to generate combinations.
Theory
Combinations are a way to count the number of ways to choose a subset of items from a larger set, where the order of selection does not matter. Combinations are used to solve problems related to permutations, where the order of selection does matter, by eliminating the permutations that represent the same combination.
Let's consider the colors Red, Green, and Blue.
If we want to find the permutation of this set, we will have:
Red, Green, Blue
Red, Blue, Green
Green, Red, Blue
Green, Blue, Red
Blue, Red, Green
Blue, Green, Red
However, if we want to find the combination of the set, we will have:
Red, Green
Red, Blue
Green, Blue
Then, as I said previously, combinations eliminate permutations that have the same subset elements, it doesn't consider the order of elements in the subset.
The formula to calculate the possible combinations of a subset is:
$$nCr = {n!\over(n-r)!r!}$$
The Code
function combinations<T>(items: T[], size: number = items.length): T[][] {
const combinations: T[][] = [];
const stack: number[] = [];
let i = 0;
size = Math.min(items.length, size);
while (true) {
if (stack.length === size) {
combinations.push(stack.map((index) => items[index]));
i = stack.pop()! + 1;
}
if (i >= items.length) {
if (stack.length === 0) {
break;
}
i = stack.pop()! + 1;
} else {
stack.push(i++);
}
}
return combinations;
}
console.log(combinations([1,2,3]))
console.log(combinations([1,2,3], 2))
In this approach, we use a stack to keep track of the indices of the items that are currently included in the combination being built. We start by initializing the stack and setting the initial index i
to 0.
We use a while loop that continues until we have processed all possible combinations. Inside the loop, we have three main conditions:
If the stack length is equal to the desired size, it means we have a complete combination. We map the indices in the stack to their corresponding items in the
items
array and add the combination to thecombinations
array. Then, we pop the top index from the stack and incrementi
to the next index.If
i
is greater than or equal to the length of theitems
array, it means we have reached the end and need to backtrack. If the stack length is 0, it indicates that we have processed all combinations and can exit the loop. Otherwise, we pop the top index from the stack and seti
to the next index.If none of the above conditions are met, it means we can add the current index
i
to the stack and incrementi
to the next index.
By iterating through these conditions, we build the combinations iteratively and add them to the combinations
array. Finally, we return the combinations
array as the output.
Conclusion
In this post, we used an auxiliary stack to help us to find the combinations of an array in Typescript. Frequently I use it to generate variations of a given input. The idea presented here can be applied in any programming language. Combinations are an interesting field in mathematics and they are very helpful in computation.