If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the permutations in JavaScript and Python. Show
Give yourself an A. Grab your copy of A is for Algorithms Retrieval PracticeRetrieval practice is the surest way to solidify any new learning. Attempt to answer the following questions before proceeding:
What is Recursion?In computer science, recursion occurs when a function calls itself within its declaration. We use recursion to solve a large problem by breaking it down into smaller instances of the same problem. Recursion consists of two things:
We use the recursive case to break the problem down into smaller instances. We use the base case to stop when there are no more problems to be solved. What is a Factorial?A factorial is the product of all positive integers less than or equal to n. We write that as n!. For example, 5!:
What is a Permutation?According to ye olde Wikipedia:
There are two types of permutations: with and without repitition. In this tutorial, we’ll work with permutations without repitition. The equation for this is:
Let’s Get MetaAsk yourself the following questions and keep them back of mind as you proceed:
How to Code the Permutations AlgorithmProgramming is problem solving. There are four steps we need to take to solve any programming problem:
Understand the ProblemTo understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:
That’s our general outline. We know our input conditions, an array of values with no duplicates, and our output requirements, an array containing all permutations, and our goal is to generate the permutations of 2 without repitition.Let’s make a plan! Make a PlanLet’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:
The first step is decomposition, or breaking our problem down into smaller problems. What’s the smallest problem we can solve? If the length of n is equal to 1, then the only permutation is:
If n is equal to 2, then our permutations are:
If n is equal to 3, then our permutations are:
Do you see a pattern emerging? It’s definitely factorial! We will also definitely need to iterate. As we saw with the combinations algorithm, we don’t know in advance how many iterations will be required. What’s the solution? Recursion! As we recalled above, recursion consists of two things:
What’s our base case?
If 2 is equal to 1, we simply return 2 wrapped in brackets.Let’s pseudocode that…
What’s the next problem we can solve? 2! That’s 2 exclamation point, not 2 factorial :) Here’s our input array:
And we need to output the following permutations:
We don’t see a pattern yet, but can you see the problem we need to solve? We can’t use the same approach as we did with the combinations algorithm because our second permutation is not in sequential order. We could swap the values, but we know that won’t scale. Or will it? :thinking-face: If you recall, the pseudocode for our swap algorithm looks like this: 1The crux of the swap algorithm is creating a 5 variable to store one of the values while we make the reassignments. We need to do the same thing here: store one of the values while we reassign the others.Easy peasy! Let’s step through this with our two element array. Because we are returning two permutations, we know we need two iterations. On the first iteration, we select 1. Let’s store it in a variable, 6. 2Now we need a way to store the remaining values. But how do we know which values are remaining? On the first iteration, 2 will remain. But on the second iteration, 1 will remain. We could write a series of conditional statements. But that’s no fun. It would be much more fun to slice it up! We can think of slicing as a conditional. If there are any values that precede the selected value, we’ll slice them off into their own array. If there are no values that preced the selected value, the method will simply return an empty array. The same goes for the values that succeed the selected value. Let’s call these values 7 and 8. 3There are now two shorter arrays for us to manage. We know we need to make the leap to recursion at some point, which means calling our 9 function. But the function only accepts one parameter. So… when life gives you two arrays, concatenate! J4F, let’s call this shorter array 0. 4We’ll catch the results of the 9 function in our 2 variable and enter the nested loop, where we’ll iterate over each value in 2 and create a new 4 by concatenating it with 6. We push 4 to 7.The next step is to pass 0 to our recursive 9 function. Let’s catch the return value in a 2 variable. 5The final step is to iterate over 2 and build our permutations. Here’s our final pseudocode: 6Execute the PlanNow it’s simply a matter of translating our pseudocode into the syntax of our programming language. How to Code the Permutations Algorithm in JavaScriptLet’s start with JavaScript… 7How to Code the Permutations Algorithm in PythonNow let’s see it in Python… 8Just like combinations, there’s a permutations method that ships with Python. We first need to import the 2 module. 9Then it’s simply a matter of calling the 9 method from 2 and pass it our list as an argument. 0According to , under the hood, it’s roughly equivalent to this: 1Evaluate the PlanCan we do better? Eh. We could add conditionals to catch edge cases and refactor it to look fancy. But hey! This is the last tutorial in this series and as they say, ‘Done is better than perfect.` What is the Big O Of the Permutations Algorithm?If you want to learn how to calculate time and space complexity, pick up your copy of The Little Book of Big O ReflectionRemember those meta questions we asked at the outset? Let’s make it stick and answer them now!
Why Do I Need to Know This?Understanding permutations will help you when you’re planning seating arrangements at a wedding. It will also help you identify when a problem might require a factorial solution, such as the Traveling Salesman Problem, in which case you would want to use dynamic programming or a heuristic algorithm. What Problem(s) Does the Combinations Algorithm Solve?Other than generating permutations, it creates more problems than it solves with its time and space complexity! Where Have We See This Or Something Like It Before?This algorithm brings us full circle, back to the first one we solved: the swap. I structured this series in this way to demonstrate a few things:
A is for AlgorithmsGive yourself an A. Grab your copy of A is for Algorithms Want to level up your problem solving skills? I write a bi-weekly newsletter about programming, problem solving and lifelong learning. Join now |