6
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Is there a reason not to use itertools.permutations? \$\endgroup\$
    – Ludisposed
    Jan 3, 2018 at 12:52
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – SylvainD
    Jan 3, 2018 at 22:03

2 Answers 2

5
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 3, 2018 at 18:44
2
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Good point, but many (most?) online judges require that you wrap the solution in a class. \$\endgroup\$
    – Daniel
    Jan 3, 2018 at 22:17
  • 1
    \$\begingroup\$ That class is necessary on leetcode, where the challenge comes from. \$\endgroup\$
    – Ludisposed
    Jan 3, 2018 at 23:35
  • \$\begingroup\$ It is a torture to listen to the man on the video (he makes me feel I am suffocating in water) \$\endgroup\$ Jan 4, 2018 at 8:28
  • \$\begingroup\$ @BillalBEGUERADJ Haha, I quite enjoyed the video last time I watched it but your comment made me laugh :) \$\endgroup\$
    – SylvainD
    Jan 4, 2018 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.