Permutations II from leetcode solution

Question

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations: [[1,1,2], [1,2,1], [2,1,1]]

There are many better solutions out there but I am interested in just the code review and how it can be made better.

Solution is exactly described here

Let's use input abc as an example.

Start off with just the last element (c) in a set (["c"]), then add the second last element (b) to its front, end and every possible positions in the middle, making it ["bc", "cb"] and then in the same manner it will add the next element from the back (a) to each string in the set making it:

"a" + "bc" = ["abc", "bac", "bca"] and "a" + "cb" = ["acb" ,"cab", "cba"] Thus entire permutation:

["abc", "bac", "bca","acb" ,"cab", "cba"]

class Solution(object):
 def permuteUnique(self, nums):
 """
 :type nums: List[int]
 :rtype: List[List[int]]
 """
 if not nums or len(nums) == 1:
 return [nums]
 output_list, output_list_copy, temp_output = [], [], []
 for num in nums:
 if not output_list:
 output_list = [[num]]
 continue
 for t in output_list:
 assigned, already_seen = False, None
 for j in range(len(t)+1):
 if already_seen == num and assigned:
 continue
 t1 = t[0:j] + [num] + t[j:]
 if j < len(t) and t[j] == num:
 assigned, already_seen = True, num
 temp_output.append(t1)
 output_list_copy += temp_output
 temp_output = []
 output_list = output_list_copy
 output_list_copy = []
 return output_list

• Ludisposed: Is there a reason not to use itertools.permutations?
• SylvainD: I'm not sure if it is too late for this but it is a good idea to use the "reinvent the wheel" tag for questions like this where you write your own version of an already existing function

Answer 1

I have a few pointers,

• Use libraries when possible, you are currently reinventing the wheel of itertools.permutations

• You could use a set() to have \$O(N)\$ lookup when finding items that are already seen.

• You should use generators instead of keeping everything in a list, this avoids high memory usage when working with large numbers

Reinventing the wheel

class Solution:
 def permuteUnique(self, nums):
 """
 :type nums: List[int]
 :rtype: List[List[int]]
 """
 def unique_perms(elements, unique):
 if len(elements) <=1:
 yield elements
 else:
 for perm in unique_perms(elements[1:], unique):
 for i in range(len(elements)):
 next_perm = perm[:i] + elements[0:1] + perm[i:]
 if tuple(next_perm) not in unique:
 unique.add(tuple(next_perm))
 yield next_perm
 return list(unique_perms(nums, set()))

Using modules

from itertools import permutations
def permute_unqiue(nums, r):
 return list(set(permutations(nums, r)))

This works by making a set() of the permutations. That removes all duplicate values, since they will hash to the same thing. Afterwards you can return the list() of unique permutations.

• noman pouigt: I knew this but just wanted to implement it as person who would be asking this would like to know how to do it given a language which doesn't have this API. Anyway will mark your answer as correct.

Answer 2

Ludusposed's answer is excellent but it can still be improved. Indeed, you don't need a class.

• Daniel: Good point, but many (most?) online judges require that you wrap the solution in a class.
• Ludisposed: That class is necessary on leetcode, where the challenge comes from.
• Billal BEGUERADJ: It is a torture to listen to the man on the video (he makes me feel I am suffocating in water)
• SylvainD: @BillalBEGUERADJ Haha, I quite enjoyed the video last time I watched it but your comment made me laugh :)