0%

• 31 Next Permutation
• 46 Permutations
• 47 Permutations II
• 60 Permutation Sequence ## 一、STL next_permutation剖析

C++ STL中，有next_permutation可以直接调用，但是这样做题就没意思啦。

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k+1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k+1] up to and including the last element a[n].

eg: 1 4 3  2  k=0 L=3  swap-> 2431 逆置-> 2134

## 二、题解

### 31. Next Permutation

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,31,3,2 3,2,11,2,3 1,1,51,5,1

C++

Java

Python

### 46. Permutations

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

For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

nums[0] + permute(nums  nums[0])  # 表示除了0以外的数的全排列

nums[1] + permute(nums  nums[1])

....

nums[n-1] + permute(nums  nums[n-1])

C++

Java

### 47. Permutations II

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

For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

C++

Java

Python

### 60. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):

"123" "132" "213" "231" "312" "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

1~n的排列数有n! ，但如果我们第一个位置上放1，那么有(n-1)!种排列。

C++

Python