6 lines Python / Ruby

  • 9

    Build the list of permutations one number at a time, insert the number into each already built permutation but only before other instances of the same number, never after. Inspired by cbmbbz's already good solution, though I then saw others had used the idea earlier.

    Python solution

    To find the last index for inserting new number n into old permutation p, I search for previous instances of n in p. But because index throws an exception if unsuccessful, I add a sentinel n at the end (which is the appropriate last insertion index then).

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

    Or as "one-liner" using reduce:

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

    Ruby solution

    def permute_unique(nums)
      nums.reduce([[]]) { |perms, n|
        perms.flat_map { |p|
          last = p.index(n) || p.size
          (0..last).map { |i| p[0,i] + [n] + p[i..-1] }

  • 0

    I referenced your answer in Permutation I and did a little change

    return [[n] + p 
                for i, n in enumerate(set(nums)) 
                for p in self.permuteUnique(nums[:nums.index(n)] + nums[nums.index(n)+1:])] or [[]]

Log in to reply

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