0. 链接

题目链接

1. 题目

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

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

2. 思路1：中介数法

例如1,2,3全排列按顺序列出，一共有3!=3*2*1=6种方式，如下:

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

获得当前排列的下一个排列的过程如下, 以1,2,3为例:

从右往左找到第一个变小的数字2
从右往左找到第一个比2大的数字3
交换2和3, 得到1,3,2
将3之后的数字按位置倒序排列(注意不是按值), 得到1,3,2

同理, 1,3,4,2的下一个排列的过程如下:

从右往左找到第一个变小的数字3
从右往左找到第一个比3大的数字4
交换3和4, 得到1,4,3,2
将4之后的数字按位置倒序排列, 得到1,4,2,3

另外，对于初始排列不是从小到大的情况，为了得到全排列，可以对数组下标执行上述的找下一个排列的步骤，直到最后一个排列完全倒序，无法再找到下一个排列，则得到了全排列。

例如

[0,-1,1]

并非一个纯升序排列
但可以取下标

[0,1,2]

依次得到

[0,1,2] --> [0,-1,1]
[0,2,1] --> [0,1,-1]
[1,0,2] --> [-1,0,1]
[1,2,0] --> [-1,1,0]
[2,0,1] --> [1,0,-1]
[2,1,0] --> [1,-1,0]

最终得到汇总结果

[
    [0, -1, 1], 
    [0, 1, -1], 
    [-1, 0, 1], 
    [-1, 1, 0], 
    [1, 0, -1], 
    [1, -1, 0]
]

3. 代码

# coding:utf8
from typing import List

class Solution:
    def next_permutation(self, nums: List[int]) -> bool:
        left_idx = None
        size = len(nums)

        i = size - 1
        while i > 0:
            if nums[i] > nums[i - 1]:
                left_idx = i - 1
                break
            i -= 1

        if left_idx is None:
            return False

        i = size - 1
        while i > left_idx:
            if nums[i] > nums[left_idx]:
                nums[i], nums[left_idx] = nums[left_idx], nums[i]
                break
            i -= 1

        l = left_idx + 1
        r = size - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

        return True

    def permute(self, nums: List[int]) -> List[List[int]]:
        rtn_list = list()
        if len(nums) <= 1:
            rtn_list.append(nums.copy())
            return rtn_list
        else:
            nums_index_list = list(range(len(nums)))
            rtn_list.append(list(map(lambda idx: nums[idx], nums_index_list)))

            while 1:
                if self.next_permutation(nums_index_list):
                    rtn_list.append(list(map(lambda idx: nums[idx], nums_index_list)))
                else:
                    break

        return rtn_list


solution = Solution()
print(solution.permute([1, 2, 3]))
print(solution.permute([1, 2, 3, 4]))
print(solution.permute([0, -1, 1]))

输出结果

[
    [1, 2, 3], [1, 3, 2], 
    [2, 1, 3], [2, 3, 1], 
    [3, 1, 2], [3, 2, 1]
]

[
    [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], 
    [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], 
    [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], 
    [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]
]

[
    [0, -1, 1], [0, 1, -1], 
    [-1, 0, 1], [-1, 1, 0], 
    [1, 0, -1], [1, -1, 0]
]