std::next_permutation
1// 手搓
2bool nextperm(string &s)
3{
4 int i, j, n = s.size();
5 if (n <= 1) return false;
6 // 找第一个降序位置,i 右边为非递增
7 for (i = n - 2; i >= 0 && s[i] >= s[i + 1]; --i);
8 if (i >= 0) {
9 // j 是第一个比 i 大的
10 for (j = n - 1; s[j] <= s[i]; --j);
11 swap(s[i], s[j]);
12 }
13 // 翻转非递增
14 reverse(s.begin() + i + 1, s.end());
15 return i >= 0;
16}
17
18// 仿STL
19template<typename BidirIt>
20bool next_permutation(BidirIt first, BidirIt last) {
21 if (first == last || next(first) == last) return false;
22 BidirIt i = last;
23 --i;
24
25 while (true) {
26 BidirIt ii = i;
27 --i;
28 if (*i < *ii) {
29 BidirIt j = last;
30 while (!(*i < *--j));
31 iter_swap(i, j);
32 reverse(ii, last);
33 return true;
34 }
35 if (i == first) {
36 reverse(first, last);
37 return false;
38 }
39 }
40}
std::reverse
1// 手搓
2void reverse(vector<int>& a, int l, int r) {
3 while (l < r) swap(a[l++], a[r--]);
4}
5
6// 仿STL
7template<typename Iter>
8void my_reverse(Iter first, Iter last) {
9 while ((first != last) && (first != --last)) {
10 std::iter_swap(first, last);
11 ++first;
12 }
13}