Generating permutations in Typescript

Motivation

Some time ago I would test how my code would behave for all combinations of a given input array. As it was not a crucial part of the system I was developing, I search for some libraries to perform this operation and save some development time. And I found good libraries in this way, such as js-combinatorics, percom.

However, I'm a curious person then I function to generate permutations of an array without using any libraries. That's what I want to show up to you.

Theory

In mathematics, permutations play a fundamental role in combinatorics and have applications in various fields. Each permutation represents a unique arrangement, and the total number of permutations depends on the number of elements being permuted. The concept of permutations is used to solve problems involving order, counting, probability, and optimization.

The formula used to calculate permutations is given by the permutation formula. It is represented as P(n, k), where n is the total number of items or elements available and k is the number of items or elements chosen. The formula for permutations is:

$$P(n, k) = {n! \over (n - k)!}$$

The "!" denotes the factorial operation, which means multiplying a number by all positive integers less than it down to 1. The permutation formula calculates the number of ways to arrange or rearrange k items from a set of n items, considering the order of selection.

Let me give you an example. Imagine we need to arrange three different colored balls: Red, Green and Blue, then n = 3. We want to arrange them in groups of 2, which means k = 2. Using the formula presented above, then:

$$P(3, 2) = {3! \over (3 - 2)!} = {3! \over 1!} = 6$$

It means we can have 6 distinct arranges for the balls, they are: [Red, Blue], [Red, Green], [Blue, Green], [Blue, Red], [Grenn, Blue], [Green, Red].

The Code

function permutation<T>(items: T[], size: number = items.length): T[][] {
  if (!size) {
    return [[]];
  }

  // If size is greater than items.length, reset size. 
  size = Math.min(items.length, size);

  return items.flatMap((item) => {
    return permutation(
      items.filter((it) => it !== item),
      size - 1
    ).map((permutation) => [item, ...permutation]);
  });
}

console.log(permutation([1, 2, 3]));
console.log(permutation([1, 2, 3], 2));

Here we check if the size of the desired permutation is equal to zero, in this case, we return an empty array. Next, we need to guarantee that the size of the permutation is less than or equal to the length of the array of items to be permuted.

The core part of the algorithm is when we iterate the input and call the permutation function recursively, passing a new array without the current item being iterated.

I suggest you simulate each step of this algorithm to understand its behavior, recursion can be confusing sometimes, but it's powerful to solve a wide range of problems.

Conclusion

In this post, we used a recursive function to generate permutations 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. Permutations are an interesting field in mathematics and they are very helpful in computation.