全排列 五种写法

BFS

def permutation(nums):
    if not nums:
        return []
    if len(nums) == 1:
        return [nums]

    res, size = [], len(nums)
    q = collections.deque()
    q.append([])

    while q:
        n = q.pop()
        if len(n) == size:
            res.append(n[:])
            continue
        for x in nums:
            if x not in n:
                q.append(n+[x])

    return res
    
#input:  [1, 2, 3]
# output: [[3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]]

DFS，用集合实现 used

# dfs(s, [], set(), res)
def dfs(s, data, used, res):
    if len(data) == len(s):
        res.append(data[:])
        return

    for i in range(len(s)):
        if i not in used:
            data.append(s[i])
            used.add(i)
            dfs(s, data, used, res)
            used.remove(i)
            data.pop()
# input:  [1, 2, 3]
# output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

DFS 改进写法，用位运算作实现 used，数据量很大的时候可以节省不少内存。在其它语言中，当数据量很大的时候，used 可以用数组来表示。譬如 64位机器上，可以 setBit = lambda arr, i: arr[i // 64] |= (1 << (i % 64))

# dfs(s, [], 0, res)
def dfs(s, tmp, used, res):
    if len(tmp) == len(s):
        res.append(tmp[:])
        return

    for i in range(len(s)):
        bit = 1 << i
        if used & bit == 0:
            tmp.append(s[i])
            dfs(s, tmp, used | bit, res)
            tmp.pop()

# input:  [1, 2, 3]
# output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

分治的思想

def permutation(nums):
    if not nums:
        return []
    if len(nums) == 1:
        return [nums]

    res = []
    for item in permutation(nums[1:]):
        for i in range(len(item)+1):
            res += [item[:i] + [nums[0]] + item[i:]]
    return res
# input:  [1, 2, 3]
# output: [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

DFS，多一点栈空间

# dfs(nums, [], res)
def dfs(nums, t, res):
    if not nums:
        res.append(t)
        return

    for i in range(len(nums)):
        dfs(nums[:i] + nums[i+1:], t + [nums[i]], res)

#input:  [1, 2, 3]
#outpu: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]