# Permutation

### Next Permutation

[31. Next Permutation (Medium)](https://leetcode.com/problems/next-permutation/)

Given a permutation, get the next permutation.

Example:

* given `[2,1,3]`, the next permutation is `[2,3,1]`.
* given `[1,2,1]`, the next permutation is `[2,1,1]`.

```cpp
/**
 * Returns true if the input `nums` is already the maximum in lexicographical order.
 */
bool nextPermutation(vector<int>& nums) {
    int i = nums.size() - 2, j = nums.size() - 1;
    while (i >= 0 && nums[i] >= nums[i + 1]) --i;
    if (i >= 0) {
        while (j > i && nums[j] <= nums[i]) --j;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
    return i >= 0;
}
```

The first section

```cpp
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) --i;
```

is looking for the last element in front of the descending subarray.

For example, `nums = [2,1,4,3]`, then `i` will point to `1` which is the last element in front of the descending subarray `[4, 3]`.

If not found, it means that the whole array is descending. The next permutation will be the reverse of the input array.

If found, we can swap it with the smallest element greater than itself, which is covered in the `if` condition.

```cpp
if (i >= 0) {
    while (j > i && nums[j] <= nums[i]) --j;
    swap(nums[i], nums[j]);
}
```

And to get the next permutation, we need to reverse the subarray starting from `nums[i + 1]` to the end.

For example, `nums = [1,6,3,5,4,2]`, then `i = 2` pointing to `3` and `j = 4` pointing to `4`. We swap `nums[i]` and `nums[j]` so swapping them gives `[1,6,4,5,3,2]`, then reverse the subarray starting from `2` to the end, getting `[1,6,4,2,3,5]`.

### Permutations (distinct digits)

[46. Permutations (Medium)](https://leetcode.com/problems/permutations/)

See [my notes here](https://github.com/lzl124631x/LeetCode/tree/master/leetcode/46.%20Permutations)

### Permutations (might contain duplicate)

[47. Permutations II (Medium)](https://leetcode.com/problems/permutations-ii/)

See [my notes here](https://github.com/lzl124631x/LeetCode/tree/master/leetcode/47.%20Permutations%20II)

### Problems

* [46. Permutations (Medium)](https://leetcode.com/problems/permutations/)
* [31. Next Permutation (Medium)](https://leetcode.com/problems/next-permutation/)
* [47. Permutations II (Medium)](https://leetcode.com/problems/permutations-ii/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuzhenglaichn.gitbook.io/algorithm/array/permutation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.