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] + p[i:] for p in self.permute(nums[1:]) for i in range(len(nums))] or []
Solution 3: Reduce, insert next number anywhere
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))
Solution 1 is very concise! It seems OJ doesn't have input
nums =  since my accepted solution returns
 and Solution 1 returns
 is just wrong. And doesn't it make your solution longer? (Did you post it somewhere already?)
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]+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
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 + p[0:] when i == 0 in range(len(nums)) in the list.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.