# One-Liners in Python

• 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))``````

• 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))``````

• 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))``````

• That does look better! Thanks!

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

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

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

• 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[[]]``````

• @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.

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

• @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.

• @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 `[]`.

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

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

• 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, [[]])``````

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