Permutations with JavaScript

Permutations are arrangements of a set of elements. [1,2,3] and [2,3,1] are two different permutations of the set {1,2,3}.

In this post, we will explore how we can generate all permutations of a given set of elements in different ways. We will encounter different topics along the way (recursion, heap and call stack, iterators and generators) that are useful in every software developer’s toolbox.

The basic approach

Before we get started coding, let’s explore the concept of generating permutations. A set with only one element has exactly one permutation: P({A}) = {[A]}. A set with more than one element can be reduced by picking an element and appending all permutations of the subset:

Let’s say we have the set {1,2,3,4,5}. We pick the element 1 and the subset {2,3,4,5}. If we have all the permutations for {2,3,4,5}, we can calculate all the permutations that start with 1: [1,2,3,4,5], [1,3,2,4,5], …

If we do that for every element in our set, we will end up with every permutation for our set. Now you might wonder: okay, but we assumed that we know the permutations for the subset, but we don’t know them yet. Well, we can apply the same algorithm to the subset, then to its subset, and so on until we get a subset of size 1. This is basic recursion.

Let’s get coding:

// version 1
function permutation(elements) {
  // these are all our permutations
  const allPermutations = [];
  // if the set size is 1, there's only one permutation
  if (elements.length === 1) return [elements];

  // for every element in our set...
  elements.forEach((firstElement, index) => {
    // we calculate the subset
    const subset = elements.filter((x, i) => i !== index);
    // recursively compute all permutations of the subset
    const subsetPermutations = permutation(subset);
    // and then prepend our picked element to each permutation of the subset
    subsetPermutations.forEach(x => {
      allPermutations.push([firstElement, ...x]);
    });
  });

  return allPermutations;
}

Then we can run this function like this:

console.log(permutation([1, 2, 3, 4]).map(x => x.join("")));
/*
[
  '1234', '1243', '1324',
  '1342', '1423', '1432',
  '2134', '2143', '2314',
  '2341', '2413', '2431',
  '3124', '3142', '3214',
  '3241', '3412', '3421',
  '4123', '4132', '4213',
  '4231', '4312', '4321'
]
*/

Running into limitations

Great! We are done, right? Well, the above code works well for small sets, but try running it for a set of size 15. After some time of computations you will be greeted with this error message:

FATAL ERROR: Reached heap limit Allocation failed - JavaScript heap out of memory

Node.js basically ran out of memory. A set with 15 elements has over 1.3 trillion permutations, which would be north of 142 PB (petabytes) of data.

So calculating all permutations at once is just not possible. We need to return each permutation once it’s calculated. Before we can do that, we need to have a closer look at how data flows in recursive functions.

Reversing the data flow

When calculating the permutations, we calculate all permutations of the subset and then prepend, which means our final permutation is calculated at the earliest instance of the recursive function execution. This means that data flows bottom-up.

Let’s reverse this data flow by passing down the prefix of the permutation into the recursive call.

// version 2
// we moved the array with all final permutations to the parameters
// we added the prefix array that will pass all previously picked elements to the subsequent recursive call
function permutation(elements, allPermutations = [], prefix = []) {
  // when there's only one element left, we end the recursion and push the final permutation into the array
  if (elements.length === 1) allPermutations.push([...prefix, elements[0]]);
  else
    // we iterate over each element that hasn't been picked yet
    elements.forEach((element, index) => {
      // and compute the subset as before
      const subset = elements.filter((x, i) => i !== index);
      // we add the picked element to the prefix and continue downward with the recursion
      permutation(subset, allPermutations, [...prefix, element]);
    });

  return allPermutations;
}

This looks like we are doing basically the same, and when we try running this with a large set again we will run out of memory, so why even bother?

Now that data is flowing top-down, we can “consume” each permutation one after another, print them to the console, or do calculations on them. We wouldn’t be able to do so with the bottom-up data flow.

Little side note: top-down is faster for calculating permutations, but some problems can be solved with a lower order of complexity when applying bottom-up data flow.

Adding callbacks

To consume permutations once they are fully assembled, we need to pass a callback function that will be called with the permutation.

// version 3
function permutation(elements, callback, prefix = []) {
  if (elements.length === 1) callback([...prefix, elements[0]]);
  else
    elements.forEach((element, index) => {
      const otherElements = elements.filter((x, i) => i !== index);
      permutation(otherElements, callback, [...prefix, element]);
    });
}

We replaced the aggregation array with a callback, which will be called with each permutation one by one. This way we can create permutations of big sets (although it will still take incredibly long to calculate 1.3 trillion permutations).

permutation([1, 2, 3, 4, 5], perm => console.log(perm));

This implementation fixes the previous problem by calling the callback function with each permutation. This way every permutation is consumed by the callback and does not have to be stored on the heap.

The problem with this approach is that it is not interruptible. This means we will call the callback with every permutation one by one. If we would like to distribute the workload over several worker threads or even network nodes, it would not be possible.

The easiest way to understand this shortcoming is to try to console.log one permutation per second of the set {1..15}.

Interrupting calculations

Interrupting a functional calculation is not so easy once you try to do it. Most would resort to a class-oriented state machine, but let’s try to keep it functional and build on top of our previous approach.

function permutation(elements, callback, prefix = [], next = () => {}) {
  if (elements.length === 1) callback([...prefix, elements[0]], next);
  // ...
}

We have introduced the next function that will be passed into our callback. This way the callback function can continue with the next calculation whenever it wants to.

Now, instead of calculating every sub-permutation, we will create work nodes that can be executed.

function permutation(elements, callback, prefix = [], next = () => {}) {
  if (elements.length === 1) callback([...prefix, elements[0]], next);
  else {
    // pay attention to the array of higher-order functions that is created here
    // we are not calculating each subnode but rather creating functions that, when called, will continue
    const subNodes = elements.map((element, index) => innerNext => {
      const otherElements = elements.filter((x, i) => i !== index);
      permutation(otherElements, callback, [...prefix, element], innerNext);
    });
    // ...
  }
}

Now we have functional nodes we can chain them together and execute the first one.

// version 4
function permutation(elements, callback, prefix = [], next = () => {}) {
  if (elements.length === 1) callback([...prefix, elements[0]], next);
  else {
    const subNodes = elements.map((element, index) => innerNext => {
      const otherElements = elements.filter((x, i) => i !== index);
      permutation(otherElements, callback, [...prefix, element], innerNext);
    });

    // firstNode -> secondNode -> ... -> lastNode -> next
    const run = subNodes.reduceRight((prevFunc, func) => {
      return () => func(prevFunc);
    }, next);

    // execute the first node
    run();
  }
}

To understand what’s happening: Imagine we start with the set {1,2,3,4}. We create 4 functions—one for each element in the set—that will calculate the subsequent parts of the permutation. These are the subNodes. Then we chain them together (onion style) so when the subNode for 1 is finished, it will call the subNode for 2 and so on. In the end, we execute the first function so the calculation continues.

Executing this beast of a function

Now let’s execute the new function that we’ve created:

permutation([1, 2, 3, 4, 5], (perm, next) => {
  console.log(perm);
  setTimeout(next, 1000);
});

Now we can interrupt and continue our execution at any time. But the above code is everything but easy to understand, and we can run into maximum call stack errors if we are not careful with how we execute the callback.

Fortunately for us, ES6 introduced generators that implement the above functionality with new syntax.

Permutations with recursive generators

If you have never heard of JS iterators/generators, you can read up on them in the mdn docs.

We can use the top-down flow from the previous implementation. With generators we don’t need callbacks; the execution will stop after each yield. Since we don’t have a callback to pass down, we need to yield every result from the recursive call below.

// version 5
function* permutationGenerator(elements, prefix = []) {
  if (elements.length === 1) yield [...prefix, elements[0]];
  else {
    for (let index = 0; index < elements.length; index++)
      // yield* returns every result one by one
      yield* permutationGenerator(
        elements.filter((x, i) => i !== index),
        [...prefix, elements[index]]
      );
  }
}

You can execute this code in the REPL console and step through each permutation with next():

> const f = permutationGenerator([1,2,3,4])
undefined
> f.next()
{ value: [ 1, 2, 3, 4 ], done: false }
> f.next()
{ value: [ 1, 2, 4, 3 ], done: false }
> f.next()
{ value: [ 1, 3, 2, 4 ], done: false }

What we see is that the next function is not just returning the next value but an object. This is the iterator interface that is used in for-loops and array spread operators. You can access it on ordinary arrays as well:

const arr = [1, 2, 3];
const iter = arr[Symbol.iterator]();
iter.next();
// { value: 1, done: false }

This means that we can use our permutation generator similarly to an array, iterate over it, and even spread it into an array if we wanted to.

const allPermutations = [...permutationGenerator([1, 2, 3, 4])];

for (const perm of permutationGenerator([1, 2, 3, 4])) {
  doSomeWorkWith(perm);
  // you can break at any time here
}

Benchmarking

Now that we have several implementations of permutations, let’s see which one is actually the most performant. To get a somewhat reliable measurement, we will run every function separately 10 times.

const range = size => new Array(size).fill().map((_, i) => i + 1);

const measureTime = (tag, func) => {
  console.time(tag);
  range(10).forEach(func);
  console.timeEnd(tag);
};

Disclaimer

I ran the code on Node.js v22.15.0. Your mileage may vary depending on the environment and hardware.

Version 4 problems

When testing version 4, I ran into the issue that nesting the next calls would quickly exceed the maximum call stack size.

measureTime("version 4", () => {
  permutation(range(9), (perm, next) => {
    next();
  });
});
// -> RangeError: Maximum call stack size exceeded

// so we need to execute the function like this
measureTime("version 4", () => {
  let nextTask;
  permutation(range(9), (perm, next) => {
    nextTask = next;
  });

  while (nextTask) {
    nextTask();
  }
});

Final results and conclusion

Here are the results from the benchmark (keep in mind that every function was executed 10 times).

version 1: 2.426s
version 2: 1.003s
version 3: 451.418ms
version 4: 529.116ms
version 5: 1.583s

v1 -> v2

We can see how much faster version 2 got compared to version 1 just by inverting the data flow. This is because v2 creates fewer throw-away arrays, leading to a smaller memory footprint and less time spent for garbage collection.

v2 -> v3

Another big speedup was when we eliminated the aggregation of all permutations and passing in a callback function.

v3 -> v4

Adding the possibility to interrupt our execution adds a bit more time because of the additional parameters and functions created.

v4 -> v5

Using recursive generators creates a lot of overhead for the engine to manage all the generator states and evaluate the yield statements.

Conclusion

Version 3 turned out to be the fastest implementation, while the recursive generator has a standard interface. If you want the best speed but absolutely need to be able to interrupt computation, then version 4 is your best option.