Generating permutations
Tags: computerscience, algorithms, data
Published: 2020-06-20 17:56:37

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:

```text
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](https://en.wikipedia.org/wiki/Combination) 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](https://en.wikipedia.org/wiki/Permutation)

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

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

{% katex %}
C(n, r) = \frac{n!}{r!(n-r)!}
{% endkatex %}

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

{% katex %}
P(n, r) = \frac{n!}{(n-r)!}
{% endkatex %}

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

## Tests

```ts
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](https://jestjs.io/) as the test runner, [TypeScript](https://www.typescriptlang.org/) as our language of choice and [TS-Jest](https://www.npmjs.com/package/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](https://repl.it/@jamesrweb/BackTrackingPermutations#jest.config.js) and [TS Config](https://repl.it/@jamesrweb/BackTrackingPermutations#tsconfig.json) 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:

{% replit @jamesrweb/BackTrackingPermutations %}

## Implementation

We will be using [TypeScript](https://www.typescriptlang.org/) 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!

```ts
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](https://en.wikipedia.org/wiki/Recursion_(computer_science)) 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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!