One-Liners in Python


  • 46

    Solution 1: Recursive, take any number as first

    Take any number as the first number and append any permutation of the other numbers.

    def permute(self, nums):
        return [[n] + p
                for i, n in enumerate(nums)
                for p in self.permute(nums[:i] + nums[i+1:])] or [[]]
    

    Solution 2: Recursive, insert first number anywhere

    Insert the first number anywhere in any permutation of the remaining numbers.

    def permute(self, nums):
        return nums and [p[:i] + [nums[0]] + p[i:]
                         for p in self.permute(nums[1:])
                         for i in range(len(nums))] or [[]]
    

    Solution 3: Reduce, insert next number anywhere

    Use reduce to insert the next number anywhere in the already built permutations.

    def permute(self, nums):
        return reduce(lambda P, n: [p[:i] + [n] + p[i:]
                                    for p in P for i in range(len(p)+1)],
                      nums, [[]])
    

    Solution 4: Using the library

    def permute(self, nums):
        return list(itertools.permutations(nums))
    

    That returns a list of tuples, but the OJ accepts it anyway. If needed, I could easily turn it into a list of lists:

    def permute(self, nums):
        return map(list, itertools.permutations(nums))

  • 3
    T

    Hi Stefan, cool solutions as always. I tried a solution here using the generator. If you have any cool ways to improve it I would love to hear it. Thanks.

    def permute(self, nums):
            def gen(nums):
                n = len(nums)
                if n == 0 : yield []
                else:
                    for i in range(n):
                        for cc in gen(nums[:i] + nums[i+1:]):
                            yield [nums[i]] + cc
            return list(gen(nums))

  • 1

    Nice work :-). Improvements? Hmm... you could remove that else:, since for n==0, the range will be empty and thus the loop won't be run anyway. But might be faster or clearer with the else, so I'm not sure what's better. I'd probably use enumerate, though. Here's one way, close to my first solution:

    def permute(self, nums):
        def gen(nums):
            if not nums:
                yield []
            for i, n in enumerate(nums):
                for p in gen(nums[:i] + nums[i+1:]):
                    yield [n] + p
        return list(gen(nums))

  • 0
    T

    That does look better! Thanks!


  • 0
    K

    Solution 1 is very concise! It seems OJ doesn't have input nums = [] since my accepted solution returns [] and Solution 1 returns [[]] :)


  • 0

    Boo, [] is just wrong. And doesn't it make your solution longer? (Did you post it somewhere already?)


  • 0
    K

    My solution is 7-line and it's too long...so I'm not going to post it...


  • 0

    Sorry,I found your "Soulution 2" isn't right,because the complier hints
    "Line 6: RuntimeError: maximum recursion depth exceeded",
    and I think two codes should be that:

        return [
                p[:i]+[nums[0]]+p[i:] 
                for i in range(len(nums)) # this line is 1st
                for p in self.permute(nums[1:]) #this line is 2ed
               ]or[[]]

  • 0

    @ShaoWavelet You're wrong. It gets accepted. And it can't exceed the maximum recursion depth unless you're configuring that to be very very small or you're calling the function with a unrealistically huge input. Also, your proposed fix doesn't make any difference.


  • 0

    Hi Stefan, thank you for sharing your nice solutions.
    Can you explain the effect of or [[]]?
    I don't understand it clearly. Thank you~


  • 0

    @J.R.Smith That's the base case. If nums is empty, my main expression gives an empty list, meaning "there are no empty permutations", which is wrong. So in that case, I replace the answer by a list containing the empty permutation.


  • 0

    @StefanPochmann Thank you for your explanation. At first, I thought the same way as yours. However, after I delete or [[]] from this code, it outputs [] even when the input is [1, 2, 3], not just [].


  • 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
    E

    Hi Stefan,thanks for the sharing! Could you please explain why we still need to return nums in Solution2? It seems that we can get nums which equals p[:0] + nums[0] + p[0:] when i == 0 in range(len(nums)) in the list.


  • 0
    O

    What does this line mean?

    return reduce(lambda P, n: [p[:i] + [n] + p[i:]
                                for p in P for i in range(len(p)+1)],
                  nums, [[]])

Log in to reply
 

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