31. Next Permutation

Leetcode Array

题目

[Medium]

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

中文题目

实现下一个排列，将排列中的数字重新排列成字典序中的下一个更大的排列。

如果这样的重新排列是不可能的，它必须重新排列为可能的最低顺序（即升序排序）。

重排必须在原地，不分配额外的内存。

以下是一些示例，左侧是输入，右侧是输出：

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路

做题目前，应该先理解排列permuation的概念，以及next permutation的含义。例如题目例子里的1，2，3的全排列，依次是：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

next permuation的含义是从上面的第$i$行到第$i+1$行，如果是最后一行，则为第1行。

首先，应该了解到在前面变换数字，会导致排列增加很多，例如从1 2 3到 3 2 1。所以既然要找到比原来的数的排列大一点的数，自然是从后往前找。如果数组从尾到前是增加的，那么就表明，从尾到前增加的这几个数字已经是最大的排列了，不能增加了。所以，我们的目标是找到从尾到前是减小的数字。

假设数组从尾到前是增加的，然后在有一个地方出现了反转，例如数组：[1，5，8，4，7，6，5，3，1]在7和4的位置出现减小，我们需要做的就是找到该数字，将数字与最接近于并大于该数的数字交换(这里是5)。交换了以后，排列立刻增加了，但是后面的排列仍旧是非常大的。所以应该将之后的数组变成升序排列，也就是将后面的数的排列降到最低。可以分为下面三个步骤：

• 从尾到前，找到反转点
• 从尾部向前找到后半区比该值（1）大的数，交换两个数
• 将后面的数组变成升序排列

也就是说如果对于一个全排列$a_1,a_2,a_3,...,a_k$来说，如果满足$a_1 < a_2 ≥ a_3 ≥ a_4 ... ≥ a_k$（所有$a_1$开头的全排列中字典序最大的情况），就说明这个全排列的下一个全排列不能再由$a_1$开头，而是$a_1$在字典中的下一个元素$a_j$（即满足$a_j > a_1$且$2 ≤ j ≤ k$的最小的$a_j$），由于任何$a_j$开头的全排列都大于$a_1$开头的全排列，所以我们寻找的全排列是$a_j$开头的最小的全排列。

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)

        # 特殊情况，空的列表或只有一个元素
        if n < 2:
            return


        # 找到从尾到前开始减小的数的下标loc
        loc = None
        for i in reversed(range(1, n)):
            # 找到了
            if  nums[i-1] < nums[i]:
                loc = i-1
                break

        # 始终没有找到，即已经是最大排列，直接反转
        if loc is None:
            nums.reverse()

        else:
            # 找到了该数字，将数字与最接近于并大于该数的数字交换
            larger_than_loc = filter(lambda x: x > nums[loc], nums[loc+1:])
            number_index = nums[loc+1:].index(min(larger_than_loc)) + loc + 1
            nums[number_index], nums[loc] = nums[loc], nums[number_index]
            # 将后面的元素变成升序序列
            nums[loc+1:] = sorted(nums[loc+1:])

参考

• https://shenjie1993.gitbooks.io/leetcode-python/031%20Next%20Permutation.html
• https://www.tianmaying.com/tutorial/LC31
• https://leetcode.com/problems/next-permutation/solution/