9-line python solution with 1 line to handle duplication, beat 99% of others :-)


  • 40

    Very similar to Permutation I, see explanations in https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution. To handle duplication, just avoid inserting a number before any of its duplicates.

    def permuteUnique(self, nums):
        ans = [[]]
        for n in nums:
            new_ans = []
            for l in ans:
                for i in xrange(len(l)+1):
                    new_ans.append(l[:i]+[n]+l[i:])
                    if i<len(l) and l[i]==n: break              #handles duplication
            ans = new_ans
        return ans

  • 14

    Nice one! Here's an even shorter and I think faster implementation, though. Got it accepted in 100 ms, achieving the coveted "Your runtime beats 100.00% of python submissions." (Well, I tried five times, they were 112, 104, 100, 104 and 116 ms).

    def permuteUnique(self, nums):
        ans = [[]]
        for n in nums:
            ans = [l[:i]+[n]+l[i:]
                   for l in ans
                   for i in xrange((l+[n]).index(n)+1)]
        return ans
    

    And for fun, a one-liner version:

    def permuteUnique(self, nums):
        return reduce(lambda a,n:[l[:i]+[n]+l[i:]for l in a for i in xrange((l+[n]).index(n)+1)],nums,[[]])
    

  • 0
    C

    Could you explain how could you come up with this condition to handle duplicate situations?
    I believe it is easy to think of inserting same number nearby, but not the "if i<len(l): break"


  • 2
    C

    It is easy to come up with we should skip the same number we meet. But that only covers intra-perm, like from “2,1” to “2,2,1” and “2,2,1”, how about the inter-perm duplicate, like from “2,1” to “2,1,2” and from “1,2” to “2,1,2”.
    When we first encounter the situation from “2,1” to “2,2,1” and “2,2,1”, if we choose to “continue” and we will insert new “2” into rightmost position to get “2,1,2” which duplicates “2,1,2” later from “1,2”.
    Why? First we start from permutation “---orig_num---” and insert new number from left to right. Once the new number is inserted right of its duplicate number, it looks like “---orig_num---insert_num---”, which can be observed as “---new_num---orig_num---” extended from another permutation “---orig_num---” by inserting insert_num at left position. Because we operate on all permutations generated from previous loop, we can always find a previous permutation to cause inter-permation duplicate.
    Therefore, we should “break”, other than “continue”, after we encounter the first same number.


  • 1
    C

    @StefanPochmann very smart by using (l+[n]).index(n) to eliminate duplicates


  • 0
    S

    Followed your Java solution in Permutation I. But I maintained a cache to keep track of the previous values.

    List<List<Integer>> permutations = new ArrayList<List<Integer>>();
            
            if(nums.length == 0)
                return permutations;
            
            HashSet<String> cache = new HashSet<String>();
            
            List<Integer> t = new ArrayList<Integer>();
            t.add(nums[0]);
            permutations.add(t);
            
            for(int i = 1; i < nums.length; i++){
                List<List<Integer>> temp = new ArrayList<List<Integer>>();
                
                for(int j = 0; j <= i; j++){
                    for(List<Integer> l : permutations){
                        List<Integer> new_l = new ArrayList<Integer>(l);
                        new_l.add(j, nums[i]);
                        if(!cache.contains(new_l.toString())){
                            temp.add(new_l);
                            cache.add(new_l.toString());
                        }
                    }
                }
                permutations = temp;
            }
            return permutations;
    

    Although this is not very fast method, also using extra memory, but couldn't come up with better solution following your Permutation I solution. Please suggest if you can give better iterative solution following your logic. Thank you in advance.


  • 7
    Z

    Very smart way to eliminate the duplicate.
    Here is my understanding about the eliminate process.

    After several times of append and other operations,
    #here I just pay attention to one element, 2's position in the inner list
    We get the current list like below:

    1. [2,x,x,x]
    2. [x,2,x,x]
    3. [x,x,2,x]
    4. [x,x,x,2]
      Of course if we replace the "x" with other elements, there should be several other lists in each row,but the position of "2" should just be same,[0],[1],[2],[3] for each row.
      The approach will traverse each list and insert the new element.
      If the new element is "2", the current "for loop" will break.
      Therefor,after the two loops,the "2" 's position in the list should be:
      [0,1]
      [0,2],[1,2]
      [0,3],[1,3],[2,3]
      [0,4],[1,4],[2,4],[3,4]
      It will actually cover all the situation of the two 2's distribution.

  • 0
    J

    Would someone please do me a favor by analyzing the time and space complexity of the implementation? Thank you very much in advance!


  • 0
    J

    @cbmbbz Hi, there! Very nice solution! But one quick question: Since we want to make sure not inserting a number before any of its duplicates, why do we handles the duplication after the insertion? I knew the code works well, but this part is kinda confusing.
    As follow:
    new_ans.append(l[:i]+[n]+l[i:])
    if i<len(l) and l[i]==n: break


  • 0
    S

    @jessicalee I think they will be exponential, as the result set is exponential. For example each digit can be at first, second, third ... last. Then the complexity is O(n^n) where n is the length of the array.


  • -2

    @chenweisomebody Your broken english is really hard to understand.


  • 0
    L

    @ja0b I think the author means 'after'.....you could go through the code to see ...


  • 0
    C

    Very smart thinking! Thanks a lot!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.