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 ofcombinations 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:

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

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

Tests

constinput:number[]=[1,2,3];constpermutations: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 withJest as the test runner,TypeScript as our language of choice andTS-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 theJest Config andTS 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 usingTypeScript 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!

functionswap<T>(array:T[],x:number,y:number):void{consttemp=array[x];array[x]=array[y];array[y]=temp;}functionpermute<T>(array:T[],start:number=0,result:T[][]=[]):T[][]{if(start===array.length-1){result.push([...array]);}for(letindex=start;index<array.length;index++){swap<T>(array,start,index);permute<T>(array,start+1,result);swap<T>(array,start,index);}returnresult;}

Thepermute function

Thepermute function is arecursive 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 inputarray

You will never use thestart orresult parameters because these are only used for each consecutive recursive call of thepermute 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 thestart index is equal to the last item of the array's index, we will stop recursing the inputarray. If we are not currently meeting the criteria of our base case, we then begin a loop going from thestart index to the end of the array.

For each item in the array, we will use a method calledbacktracking 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 theswap function to swap the item from thestart index and the item at the currentindex, running a recursive call of thepermute function and finally re-swapping the items from thestart index and currentindex 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 originalarray 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 thefactorial result of the count of items in the inputarray.

This means that an inputarray 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 inputarray as small as possible at any time to keep things performant.

Theswap function

Theswap function takes in 3 parameters:

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

We copy the item at positionx in thearray, set the item at positionx to the value of the item at positiony and finally set the item at positiony to the item that used to be at positionx.

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!