剑指offer 17 +全排列问题

话不多说，直接手撕一个正常全排序代码。

#define _CRT_SECURE_NO_WARNINGS
#include <tuple>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
int INF = 1 << 30;

int N = 3;

void add(string& s, int idx, vector<int>& traversed)
{
    if (idx >= s.size())
    {
        printf("%s\n", s.data());
        return;
    }
    for (int i = 1; i <= N; i++)
    {
        if (!traversed[i])
        {
            traversed[i] = 1;
            s[idx] = '0' + i;
            add(s, idx + 1, traversed);
            traversed[i] = 0;
        }
    }
}

int main()
{
    vector<int> traversed(N+1, 0);
    string s(N, '0');
    add(s, 0, traversed);
}

从上述代码可以看到，和刚才的算法很类似，只不过这个要加一个限制条件，即放过的不能再放，这样就很ok了。优先放小的，再放大的，小的放过了再轮到大的。

然后就是考虑下如何找下一个排列和上一个排列？
下一个排列：要找最靠右的两个能交换的数交换（利用单调思想），然后把后面的变成最小（逆一下）
找上一个排列也是一样的，利用单调，使交换的两位尽可能靠右，然后让右边的数变最大（逆）

全排列生成和找上一个/下一个排列还是有区别的，是不同的思想。