Generating permutations

I like to think of permutations as simply:

The rearrangement of a collection of elements into each possible new arrangement of those elements.

Let's demonstrate what the permutations of a dataset could look like:

Dataset: [1, 2, 3]
Permutations: [
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,2,1],
  [3,1,2]
]

Building an algorithm to generate permutations of a collection is also a common technical interview test too and so it is a good thing to be aware of.

Now, for those familiar with the concept of combinations you may remember that permutations and combinations are somewhat related but be aware that there is a difference between these concepts.

In mathematics, permutation is the act of arranging the members of a set into a sequence or order, or, if the set is already ordered, rearranging its elements—a process called permuting. Permutations differ from combinations, which are selections of some members of a set regardless of order.

Source: Permutations Wiki

We can see this inherent difference as we write out the maths behind each concept.

The count of possible combinations (C) is defined as:

$$C(n, r) = \frac{n!}{r!(n-r)!}$$

The count of possible permutations (P) is defined as:

$$P(n, r) = \frac{n!}{(n-r)!}$$

With this, we can see the inherent difference between the two concepts.

Tests

const input: number[] = [1,2,3];
const permutations: number[][] = permute(input);

describe("permutations", () => {
  it("returns the correct number of permutations", () => {
    expect(permutations.length).toBe(6);
  });

  it("returns the correct permutations", () => {
    expect(permutations).toEqual([
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,2,1],
      [3,1,2]
    ]);
  });
});

The tests are written with Jest as the test runner, TypeScript as our language of choice and TS-Jest as the glue between the two since Jest doesn't support TypeScript out of the box.

If you want to know how to get Jest and TypeScript to work together then you can check the Jest Config and TS Config files from the repl for this article.

If you wish to look at the code, config, or just run the tests, you can do so with the repl below:

Implementation

We will be using TypeScript for our implementation but don't be alarmed if you haven't used that before as we will be diving into the implementation step by step!

function swap<T>(array: T[], x: number, y: number): void {
  const temp = array[x];
  array[x] = array[y];
  array[y] = temp;
}

function permute<T>(array: T[], start: number = 0, result: T[][] = []): T[][] {
  if(start === array.length - 1) {
    result.push([...array]);
  }

  for(let index = start; index < array.length; index++) {
    swap<T>(array, start, index);
    permute<T>(array, start + 1, result);
    swap<T>(array, start, index);
  }

  return result;
}

The permute function

The permute function is a recursive function which takes in 3 parameters:

1. array is the collection that we will be generating permutations from
2. start is the index of the array to begin from
3. result is an array of arrays, each of which will contain items of the same type as the items of the original input array

You will never use the start or result parameters because these are only used for each consecutive recursive call of the permute function. If you really wanted to though, you could provide arguments for these although it is not recommended to do so.

As we enter the function body we begin with the "base case" as it is usually named and all this does is provide us a way to break the recursive calls based on a pre-defined definition of done.

In our case, if the start index is equal to the last item of the array's index, we will stop recursing the input array. If we are not currently meeting the criteria of our base case, we then begin a loop going from the start index to the end of the array.

For each item in the array, we will use a method called backtracking which is a way of running an operation and then undoing it again after we complete some action when required.

In our case, we are using the swap function to swap the item from the start index and the item at the current index, running a recursive call of the permute function and finally re-swapping the items from the start index and current index back to their original places once each recursive cycle is completed.

You can imagine this as a tree, we take each item, swap it with every other item and swap those iterations with every other iteration before resetting everything in the original array back to normal and returning the result of each iteration in the tree.

This becomes a problem no matter how it is implemented once the dataset grows over ten or so items however since the count of possible permutations is mathematically tied to the factorial result of the count of items in the input array.

This means that an input array with 4 items will produce 24 permutations but one with 8 items will produce 40,320 and one with 20 items will produce 2,432,902,008,176,640,000. This means we should keep the input array as small as possible at any time to keep things performant.

The swap function

The swap function takes in 3 parameters:

1. An array
2. The first (x) index for the swap
3. The second (y) index for the swap

We copy the item at position x in the array, set the item at position x to the value of the item at position y and finally set the item at position y to the item that used to be at position x.

Pretty simple, right?

Conclusions

Permutations are a common occurrence and have use cases in many real-life scenarios and industries such as cyber-security, cryptography, and transportation for example.

In the medical industry, medicine manufacturers use permutations to analyze and predict the spreading of various diseases, genetic sequences, analysis of drug-safety data, and to analyze various permutations of drugs and chemicals as well in relation to the desired outcome of treatment.

Even if it isn't relevant to your work, it is a common coding test and so knowing the theory and practice are good things to have in your back pocket. The best part is that if we know how to swap items, backtracking based on a single index is possible as we have seen in the implementation above and I personally find this method of generating permutations the easiest to remember and implement and I hope it is the same case for you.

I hope this post brought you some value and helped to clear up what permutations are, what real-world use cases for permutations are out there and how we can generate them using swapping, recursion, and backtracking!