Today I’m going to be explaining permutations by showing the logic behind this problem and how to approach it. I’ve been reading about permutations and I’ve noticed that permutations are a recurring must learn interview question so we can all benefit from reviewing it. Here we go!
Permutations:
Permutations are the several possible variations in which a collection of values can be ordered or arranged.
Today we are going to be taking an array of a, b and c as an example.
// array we'll be using
[ 'a', 'b', 'c' ]
// result of permutation
[
[ 'a', 'b', 'c' ],
[ 'a', 'c', 'b' ],
[ 'b', 'a', 'c' ],
[ 'b', 'c', 'a' ],
[ 'c', 'a', 'b' ],
[ 'c', 'b', 'a' ]
]
The Concept:
We need to get all the possible variations and we can start with the character 'a' and put it at the beginning, the middle and the end. First we swap the first character with itself and it gives us 'a' in one branch, then 'b' in another branch and the same with 'c'.
Recursion:
This problem needs to use recursion because we are doing the same thing every time with the exception that we shift to the next character every cycle with the end of the cycle been the end of the array. To get a better understanding of why we need to use recursion let’s think about it as a tree, and our solution will be all the results together at the end of that tree:
To make sense of this picture, I would like to separate it in Five Steps:
First Step:
In the example above we are going to iterate through the array and take the first value (index = 0) which is ['a'] and remove it from our possible values to use. That leaves us with ['b', 'c'].
Second Step:
Now we are going to be iterating through the array again starting at first value (index = 0) which now is ['b'], and we will remove it from our possible values to use. Now we have ['a','b'] and we have ['c'] left.
Third Step:
Then we are going to iterate through the array again starting at the first value (index = 0) which now is ['c']. Once we hit this last value we end up with an empty array which then will hit our base case and push the values to our results array
Fourth Step:
This is the moment we have to go back to the Second Step
but because we already iterated through that step we are going to go back to the First Step. Here is when we do the index shift because we already iterated through index 0. Now we are going to have to increment our index to index 1 and that will add ['c'] to our answer which will be removed from the values we can use. Now we have ['a','c'] and we have ['b'] left
Fifth Step:
Now we will iterate to index 0 again and that would be the letter ['b'] and remove it from the values we can use which will leave us with an empty array and then we will be ready to push our values to the our results array. Now let's repeat the whole process again. We will go back to our Origin array and then increment to index 1 which will take us to our letter ['b']. We will perform all the steps through ['b'] and ['c'].
Here is an implementation of a permutation function:
// permutation function
const permutations= (array) => {
// Our results container
const results = [];
// helper function
const permute = (arr, perm = []) => {
// if the array is empty
if(arr.length === 0) {
// push the perm values to results
results.push(perm);
} else {
// iterate through the array of ['a','b','c']
for(let i = 0; i < arr.length; i++) {
// create a copy of the array to keep it a pure function
let current = [...arr];
// move to the next index of our array
let nextArr = current.splice(i, 1);
/* call our permutation with our copy array
and our permutation container joining it with our next value of the array */
permute([...current], perm.concat(nextArr));
}
}
}
// call the function on our array
permute(array);
// return the result
return results;
}
permutations(['a', 'b', 'c']);
/* result => [
[ 'a', 'b', 'c' ],[ 'a', 'c', 'b' ],[ 'b', 'a', 'c' ],
[ 'b', 'c', 'a' ],[ 'c', 'a', 'b' ],[ 'c', 'b', 'a' ]
] */
Time Complexity
The time complexity is the same as the number of items produced. The number of permutations of any combination of n is n!. We will have to iterate over n! permutations which makes the time complexity to complete the iteration O(n!).
Conclusion:
To find the permutations of a value has a very high time complexity but that is the price you have to pay if you want to get all the possible solutions.
I hope you enjoyed the reading!
Top comments (0)