Hoarding programming problems for you!

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Permutations challenge – Iterative solution

Sharing is caring!

Problem statement
Given a list, nums, of distinct numbers, return all possible permutations.

Sample input

Sample output

Solution
In another post we showed how this problem can be solved using a recursive technique by swapping. We stumbled upon a nice iterative solution that we thought might be worth sharing.

The idea is to start at an empty list of list ans = [[]]. We then iteratively are going to expand our ans list. We are going to do this by iterating over every number n in nums and insert it at every possible position in every list that is currently in ans.

Let nums = [1,2,3]. And let ans = [[]]. The first number is 1 and the first list in ans is []. We then make a copy of [] and add 1 at every position in [] which results in [1]. We add the newly created list to our new answer list and replace ans with that and repeat. The next number is 2. We then iterate over ans and add 2 at every possible position in every list we iterate over in ans. The only list in ans is [1]. So we make a copy and add 2 at position 0 and then make another copy and add 2 at position 1. We add the resulting lists to our new answer list and replace ans with that list, resulting in ans = [[2,1], [1,2]]. The next number in nums is 3. Again, we then iterate over ans ([[2,1], [1,2]]) and add 3 at every possible position in every list in ans. So for list [2,1] in ans we get [3,2,1], [2,3,1], [2,1,3] and for [1,2] we get [3,1,2], [1,3,2], [1,2,3] which results in our new and final ans.

Full code