Next Permutation

Problem

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

---

Note

• STL 中vector找最小元素

---

Idea

搞清楚输入顺序和数组的顺序 1 2 3 ===> 1 (a[2]), 2(a[1]) 3(a[0])

递归来解. 从最后两个元素开始，如果a[i-1] > =a[i]那么检查再往前的。如果找到a[i-1] < a[i] 找到子树组(a[i] - a.end()) 中第一个大于a[i-1]的元素a[j]，交换 a[j]和a[i-1]， 最后a[i] - a.end()重新排序.

---

Solution