算法题--全排列II

image.png

0. 链接

题目链接

1. 题目

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,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

由于起始排列不一定是升序排列，所以终止排列也不一定是降序排列，按照上述步骤，降序排列的下一个排列是取不到的，为了能构成一个轮回，当遇到纯降序排列时，则全部倒序一下，就得到了下一个排列；相应的，终止条件变成回到初始排列就意味着轮回了一圈，停止即可。

3. 代码

# coding:utf8
from typing import List


class Solution:
    def next_permutation(self, nums: List[int]):
        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:
            l = 0
            r = size - 1
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        else:
            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 nums

    def is_same(self, nums, nums_copy):
        for i in range(len(nums)):
            if nums[i] != nums_copy[i]:
                return False
        return True

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        rtn_list = list()
        if len(nums) <= 1:
            rtn_list.append(nums.copy())
            return rtn_list
        else:
            nums_copy = nums.copy()
            rtn_list.append(nums.copy())
            while 1:
                if not self.is_same(self.next_permutation(nums), nums_copy):
                    rtn_list.append(nums.copy())
                else:
                    break

        return rtn_list


solution = Solution()
print(solution.permuteUnique([1, 2, 1]))
print(solution.permuteUnique([1, 1, 2]))
print(solution.permuteUnique([1, 1, 2, 3]))

输出结果

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

4. 结果

image.png