Today, we have another programming challenge from Leetcode: https://leetcode.com/problems/permutations/.
Table of Contents
The Challenge
This challenge requires us to write a function called permute() that accepts a list of distinct numbers and returns a list with all permutations of the numbers in the input list.
For instance, if the input list is [1, 2, 3], the function should return [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
Expected Results
To test your function, you can run the following statements:
print(permute([1, 2]))
print()
print(permute([1, 2, 3]))
print()
print(permute([1, 2, 3, 4]))
You should get the following output:
[[1, 2], [2, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
Suggested Approach
We’ll be using recursion to solve the challenge in this post. As mentioned in previous posts, recursion is an excellent approach to use when the solution to the problem depends on solutions to smaller instances of the same problem.
If you are unfamiliar with recursion, I strongly recommend that you check out previous posts on recursion (here, here and here). We’ll be using recursion with a for loop today, which is slightly more complicated than what we did in previous posts.
How to permute numbers Mathematically?
Before proceeding with the programming for today’s challenge, we need to first know how to permute numbers mathematically. The most systematic way to do it is to use a tree diagram. Suppose we want to permute the numbers 1, 2, and 3. The diagram below shows how we can do it.
The first number can be 1, 2 or 3.
If the first number is 1, the second number can be 2 or 3 (shown in orange above).
If the second number is 2, the third number must be 3. This gives us 1, 2, 3 as the result (1st result above).
If the second number is 3, the third number must be 2. This gives us 1, 3, 2 as result (2nd result above).
The rest of the results can be obtained using the same logic.
How to permute numbers using recursion?
A tree diagram allows us to systematically list all possible permutations of a given set of numbers. We can modify this diagram to represent the solution as a recursive solution.
To do that, we need to look at the tree diagram differently. Instead of listing all possible branches of the diagram, we can consolidate the branches for the second and third numbers, as shown in the diagram below:
Notice how we consolidated the branches for the 2nd and 3rd numbers into three recursive calls?
For instance, the orange branches in the original solution are replaced with the recursive call “Permute 2, 3” in the solution above.
Permute 2, 3 gives us the results (2, 3) and (3, 2). When we append these results to the first number (1), we get the results (1, 2, 3) and (1, 3, 2), which are the first two results in the original diagram.
Based on the example above, we see that to solve the permutation of (1, 2, 3), we can solve the permutations of (2, 3), (1, 3) and (1, 2) and append their results to the respective first numbers.
In other words, we can solve the permutation of three numbers by solving a smaller instance of the same problem (i.e. by solving the permutations of two numbers).
The permutation of 2 numbers (such as 2 and 3) can in turn be solved by solving the permutations of 1 number and appending the results to the preceding numbers.
The permutation of 1 number is known as the base case. This is the case that stops the recursion.
The permutation of a single number is simply the number itself. Hence, we do not need to make any further recursive calls to get the value.
Once the base case is reached, we can append the result of the base case to the preceding numbers to get the permutations.
Suggested Solution
Let’s look at how we can implement the recursive solution above in Python. While the concept is complicated, the implementation is actually very simple and can be done in a few lines.
The solution is given below:
def solve(path, nums, result):
if len(nums) > 1:
for i in range(len(nums)):
solve(path + [nums[i]], nums[:i] + nums[i+1:], result)
else:
result.append(path + [nums[0]])
def permute(nums):
path = []
result = []
solve(path, nums, result)
return result
Here, we first define a function called solve() that has three parameters – path, nums and result.
path stores the numbers that precede a recursive call, nums stores a list with the numbers to permute, and result is a two-dimensional list that stores the results. We’ll illustrate what each of them does in the example later.
Inside the solve() function, we check the length of nums. If it is greater than one (i.e. there is more than one number to permute), we use a for loop to iterate through the numbers in the list and call the solve() function recursively.
If the length of nums is not greater than 1, we append path + [nums[0]] to the result list. This represents the base case. After appending path + [nums[0]] to result, we do not make any more recursive calls.
Confused? Don’t worry, we’ll run through an example later.
Next, let’s look at the permute() function. This function has one argument – nums.
Inside the function, we declare and initialize two empty lists – path and result – and use them to call the solve() function on line 12.
After calling the solve() function, result will no longer be an empty list. Instead, it’ll store all the permutations of nums. On line 13, we return the value of result.
With that, the solution is complete.
Let’s go through a concrete example now.
Suppose we want to permute the numbers 1, 2, 3, we’ll call the permute() function with the line
permute([1, 2, 3])
When we do that, Python initializes two empty lists – path and result – on lines 10 and 11 and uses them to call the solve() function (on line 12), with the following arguments:
path = []
nums = [1, 2, 3]
result = []
Inside the solve() function, as len(nums) equals 3, the if block is executed.
Inside the if block (lines 3 and 4), we have a for loop.
This for loop is represented by the blue arrows in the diagram below:
For each of the blue arrows, we call the solve() function to solve the remaining numbers recursively. For instance, for the orange branch, we have the following values:
i = 0
First argument =
path + [nums[i]] =
[] + [nums[0]] =
[1]
Second argument =
nums[:i] + nums[i+1:] =
nums[:0] + nums[1:] =
[] + [2, 3] =
[2, 3]
Third argument =
result =
[]
Hence, we call the solve() function as follows:
solve(path + [nums[i]], nums[:i] + nums[i+1:], result)
= solve([1], [2, 3], [])
For the red branch, we have the following values:
i = 1
First argument =
path + [nums[i]] =
[] + [nums[1]] =
[2]
Second argument =
nums[:i] + nums[i+1:] =
nums[:1] + nums[2:] =
[1] + [3] =
[1, 3]
Third argument =
result =
[]
Hence, we call the solve() function as follows:
solve(path + [nums[i]], nums[:i] + nums[i+1:], result)
= solve([2], [1, 3], [])
Using the same logic, you should be able to figure out the values for the black branch yourself.
Next, let’s see what happens when we execute the solve([1], [2, 3], []) recursive call (represented by the orange branch in the diagram above).
For this recursive call, we have the following values:
path = [1]
nums = [2, 3]
result = []
Inside the solve() function, the if block is executed again as nums equals [2, 3]. In other words, len(nums) is greater than 1.
This results in the following two recursive calls:
When i = 0,
solve([1, 2], [3], [])
When i = 1
solve([1, 3], [2], [])
When we execute the solve([1, 2], [3], []) recursive call (line 2 above), nums equals [3].
The if condition fails as len(nums) equals 1, which is no longer greater than 1. Hence, the else block is executed.
This block simply appends path + [nums[0]] (i.e. [1, 2] + [3] = [1, 2, 3]) to the result list, without making any further recursive calls.
Similarly, when we execute the solve([1, 3], [2], [])) function call (line 5 above), path + [nums[0]] (i.e. [1, 3] + [2] = [1, 3, 2]) is appended to result and the recursion ends.
The same logic applies to the red and black branches in the diagram above.
After we end all recursive calls, result contains all the possible permutations and we return its value on line 13.
That’s it.
Recursion can be a confusing concept to grasp, especially when we make multiple recursive calls using a for loop. Take your time to go through this post slowly to fully appreciate it.