Permutations I

Finding permutations of elements in an array, is a fairly simple problem with the usage of recursion and backtracking.

In this article, adding a template to help with these kind of problems.

Example Problems:

• Permutations
• Permutations II

In the two problems the only difference is that in one problem all the numbers are unique and in other it is not. If all the numbers are not unique in the array then the number of permutations decreases by a factor of similar numbers factorial i.e. if there are N Numbers and x & y number of numbers are same then number of permutations will be N!/x!y!. So in case of an array like [1, 1, 2, 2] there are only 6 permutation 4!/2!2! which are [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]].

To simulate permutation in the code. Put a unique character at the each of the positions in the array and permute the rest of the array using the same logic recusively.

Sample code is given:

def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        sol = []
        def helper(nums: List[int], start: int, sol: List[List[int]]):
            if start == n: # Base case, all the elements are part of the solution, add as part of the solution.
                sol.append(nums.copy())
                return
            for i in range(start, n):
                nums[i], nums[start] = nums[start], nums[i] # Put i as the start character
                helper(nums, start + 1, sol)
                nums[i], nums[start] = nums[start], nums[i] # Revert back i where it was.
        
        helper(nums, 0, sol)
        return sol

Above code is simple, but only works with unique numbers in the array. With O(N!) runtime and O(N) recursive stack space.

The reason why above code only works for unique characters is because, in case of multiple same numbers each can take the same position resulting in same permutations. So need to limit such that same numbers only take the position once. So using a set to filter out will work.

def permuteUniq(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        sol = []
        def helper(nums: List[int], start: int, sol: List[List[int]]):
            if start == n:
                sol.append(nums.copy())
                return
            seen = set() # declare a set
            for i in range(start, n):
                if nums[i] not in seen: # First check in the element is in the set
                    seen.add(nums[i]) # Add the element to the set
                    nums[i], nums[start] = nums[start], nums[i] # Put i as the first character by swaping
                    helper(nums, start + 1, sol)
                    nums[i], nums[start] = nums[start], nums[i] # Revert back i where it was.
        
        helper(nums, 0, sol)
        return sol

This is great! only problem is the space requirement has now increase to O(N^2) as the set will grow upto N elements in each recursive call and there will be N such recursive call.

We can do better, but that changes the main permutation template. Rather than swapping numbers, we need to create sub-solution and only append unique elements in the sub-solution.

Using a counter to count the number of times a number occurs in an array, you can solve both the problems:

    def permute(self, nums: List[int]) -> List[List[int]]:
        l = len(nums)
        sol = []
        seen = Counter(nums) # A map of number and times it is seen in array.
        def helper(st: List[int], sol: List[List[int]]):
            if len(st) == l:
                sol.append(st.copy())
                return
            for n in seen:
                if seen[n] > 0: # Add only if the number number not already used.
                    seen[n] -= 1 # Number has been used, decrement the count so it is not used again.
                    st.append(n) # Append to the partial solution
                    helper(st, sol)
                    st.pop() # Pop from the partial solution
                    seen[n] += 1 # Number count can be reseted again.
        
        helper([], sol)
        return sol

The above code uses O(N) space which is of the Counter, Stack (partial solution), recursive stack.

In further articles will be discussing more problem templates related to permutations and combinations.