Combinations in TypeScript

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:

1. Red, Green, Blue

2. Red, Blue, Green

3. Green, Red, Blue

4. Green, Blue, Red

5. Blue, Red, Green

6. Blue, Green, Red

However, if we want to find the combination of the set, we will have:

1. Red, Green

2. Red, Blue

3. 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:

1. 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 the combinations array. Then, we pop the top index from the stack and increment i to the next index.

2. If i is greater than or equal to the length of the items 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 set i to the next index.

3. If none of the above conditions are met, it means we can add the current index i to the stack and increment i 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.