leetcode

Permutations

Permutations 排列

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, [], res)
        return res
    def dfs(self, nums, path, res):
        print '----------------BEGIN------------------'
        print 'nums =', nums
        if not nums:
            res.append(path)
            print 'res append =', res
        for i in xrange(len(nums)):
            print 'i = %d' % i
            print 'nums[:%d] =' % i, nums[:i], '+ nums[%d:] =' % (i + 1), nums[i+1:]
            print 'path =', path, '+ nums[%d] =' % i, nums[i]
            print 'res =', res
            self.dfs(nums[:i] + nums[i+1:], path+[nums[i]], res)
            print '----------------END-----------------\n'

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
In [432]: s = Solution(); print s.permute([1, 2])
----------------BEGIN------------------
nums = [1, 2]
i = 0
nums[:0] = [] + nums[1:] = [2]
path = [] + nums[0] = 1
res = []
----------------BEGIN------------------
nums = [2]
i = 0
nums[:0] = [] + nums[1:] = []
path = [1] + nums[0] = 2
res = []
----------------BEGIN------------------
nums = []
res append = [[1, 2]]
----------------END-----------------
----------------END-----------------
i = 1
nums[:1] = [1] + nums[2:] = []
path = [] + nums[1] = 2
res = [[1, 2]]
----------------BEGIN------------------
nums = [1]
i = 0
nums[:0] = [] + nums[1:] = []
path = [2] + nums[0] = 1
res = [[1, 2]]
----------------BEGIN------------------
nums = []
res append = [[1, 2], [2, 1]]
----------------END-----------------
----------------END-----------------
[[1, 2], [2, 1]]

Recursive, insert first number anywhere

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        for i in range(len(nums)):
            for p in self.permute(nums[1:]):
                res.append(p[:i] + [nums[0]] + p[i:])
        return nums and res or [[]]

Recursive, take any number as first

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        for i, n in enumerate(nums):
            for p in self.permute(nums[:i] + nums[i+1:]):
                res.append([n] + p)
        return res or [[]]

Reduce, insert next number anywhere

1
2
3
4
5
6
7
8
9
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return reduce(lambda P, n: [p[:i] + [n] + p[i:]
                                for p in P for i in range(len(p)+1)],
                  nums, [[]])

One-Liners in Python

leet code