31. Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

题目大意
找到一个排列按照字母表顺序的情况下，下一个更大的排列是多少。如果已经是最大的，那么应该翻转。必须原地翻转。

解题方法
逆序数字交换再翻转
很有技巧的题目。

先找到从后向前数，第一个降序的位置，把此位置后面的翻转。再把这个降序数字和后面第一个比它大的位置交换即可。

首先说一下这题怎么想到的。有如下的一个数组

1　　2　　7　　4　　3　　1

下一个排列为：

1　　3　　1　　2　　4　　7

观察可以发现，再给出的数组中，2之后的数字都是降序排列的，我们把2后面第一个比2大的数字放到最前面，然后让3后面的数字升序排列。

简单思路的证明：从7开始是降序的，也就是说7 4 3 1不可能通过重新排列构成更大的数字。如果要得到next permutation，那么必须把2这个位置的数字给换掉才行，而且只能换成比2大的数字在才能使next permutation > current permutation.至于换成多大的数字，很明显的需要换成在2后面的数字中刚好比2大的数字，证明可以使用反证法来说明换成其他数字要么比当前数字小，要么大于正确的next permutation.

下面这个做法是先逆序再交换，本质和上面的证明一样：

如果从第n个数字到最后都是递减的并且第n-1个数字小于第n个，说明从第n个数字开始的这段序列是字典序组合的最后一个，在下一个组合中他们要倒序变为字典序第一个，然后从这段序列中找出第一个大于第n-1个数字的数和第n-1个数字交换就可以了。

举个栗子，当前组合为12431，可以看出431是递减的，同时4>2，这样我们把431倒序，组合就变为12134，然后从134中找出第一个大于2的数字和2交换，这样就得到了下一个组合13124。对于完全递减的组合例如4321在倒序之后就可以结束了。

代码如下：

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)
i = n – 1
while i > 0 and nums[i] <= nums[i – 1]:
i -= 1
self.reverse(nums, i, n – 1)
if i > 0:
for j in range(i, n):
if nums[j] > nums[i-1]:
self.swap(nums, i-1, j)
break

def reverse(self, nums, i, j):
“””
contains i and j.
“””
for k in range(i, (i + j) / 2 + 1):
self.swap(nums, k, i + j – k)

def swap(self, nums, i, j):
“””
contains i and j.
“””
nums[i], nums[j] = nums[j], nums[i]

也可以先进行交换，然后再翻转。比如Leetcode的这个解答方式：

C++代码如下：

class Solution {
public:
void nextPermutation(vector<int>& nums) {
const int N = nums.size();
int i = N – 2;
while (i >= 0 && nums[i] >= nums[i + 1]) –i;
int j = N – 1;
if (i >= 0) {
while (nums[j] <= nums[i]) –j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
库函数
这个算我第一次觉得C++让人惊呆吧，有next_permutation函数，而且是原地操作。

class Solution {
public:
void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(), nums.end());
}
};
原文链接：https://blog.csdn.net/fuxuemingzhu/article/details/82113409