# Permutations challenge – Iterative solution

**Problem statement**

Given a list, `nums`

, of distinct numbers, return all possible permutations.

**Sample input**

1 |
[1,2,3] |

**Sample output**

1 2 3 4 5 6 7 8 |
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] |

**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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ ans = [[]] for n in nums: new_ans = [] for perm in ans: for i in range(0, len(perm) + 1): new_ans.append(perm[:i] + [n] + perm[i:]) ans = new_ans return ans def main(): solution = Solution() print(solution.permute([1, 2, 3])) if __name__ == "__main__": main() |