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

[1,2,3]

Sample output

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

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()