Leetcode46-Permutations(Python3)

46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

My Solution

import itertools
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return list(itertools.permutations(nums))

Reference (转)

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