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,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1
STL库中有next_permutation函数
class Solution {
public:
void nextPermutation(vector<int> &num) {
next_permutation(begin(num), end(num));
}
};
template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
if (first == last) return false;
BidirIt i = last;
if (first == --i) return false;
while (1) {
BidirIt i1, i2;
i1 = i;
if (*--i < *i1) {
i2 = last;
while (!(*i < *--i2));
std::iter_swap(i, i2);
std::reverse(i1, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}
首先进行的是对两个迭代器的检查。如果迭代器之间的值为空或者只有一个元素，那么没什么可以做的。
之后，因为要找的是值比当前值大的下一个permutation，所以需要令迭代器i指向如下的结构：
- (dummy) ...... a2 a4 a3 a1
- |
所指的位置是位于容器最后面的按照从大到小顺序的元素（a4, a3, a1）之前的一个元素（a2）。这个元素a2必然小于它后面的那个元素，也就是后面排列中最大的元素a4。这么一段的目的是找到位于容器末尾已经达到可能的最大值的部分。然后下面要做的是找到这一段最大值在添加了前一个元素之后可能产生的最小值。
接下来寻找的是a2对应的位置。依次从后面向前寻找到一个不小于a2的元素，这里是a3。交换a2和a3，得到：
- (dummy) ...... a3 a4 a2 a1
- (dummy) ...... a3 a1 a2 a4