1、用递归（DFS）和非递归两种方式输出一个序列的全排列；
2、找到当前序列的下一个和上一个字典序。
全排列和字典序
- 一个序列的全排列是序列中元素所有可能的排列，排列方式共有n!个。
- 一个序列的字典序可以理解为，先把其中的元素按照从小到大的顺序排好，再对这个序列进行全排列，则所有得到的序列呈字典序。
递归方式输出全排列
递归的思想即DFS，如下图所示。
假设原始序列为，每一种排列方式的第一个元素都有3种选择方式，选择a之后剩下两个元素，因此剩两种选择方式，再选择b则只剩下c，这样选择就得到了一种排列abc，三个元素一共有3！=6中排列方式。
将上述思路转换成递归算法，即设计一个函数，它的作用是：在给定的序列中依次选择一个元素，把这个元素拼接到已有的排列，再对其余序列重复调用，直到剩下元素为0。
需要注意的两点：一是当选择一个元素后，对剩下的序列执行当前函数，然后为了实现下一种可能，要撤销这一步的操作；二是为了避免重复选择，需要额外设置一个标记数组，指示每个元素有没有在已有的排列里。
从前往后选择元素，如果初始的序列是从小到大的排列，那么就可以得到这个序列的字典序；如果是乱序的排列，则可以得到这个序列的全排列。
代码的功能为：输入一个数字n，得到从1到n这个序列的全排列。
int n;
vector<int> arr; //初始序列，假设为1到n的顺序数组
vector<int> flag; //标记数组，初始全为0，已选择的元素位置为1
//递归函数，深度优先搜索，参数cur代表已经排好的序列
void dfs(vector<int> cur) {
//如果已排好的序列长度等于元素总个数，那么一条路走完，输出这个序列
if (cur.size() == n) {
for (int i = 0; i < n; i++) {
cout << cur[i]<<" ";
}
cout << endl;
}
//如果没到头，说明还有元素待选，就按顺序依次选择加到cur中
for (int i = 0; i < n; i++) {
//首先得是已有序列中没有挑选过的元素
if (flag[i] == 0) {
//把它选上，加到cur后面，对应位置标注为1
flag[i] = 1;
cur.push_back(arr[i]);
//再对剩下的序列进行同样的操作
dfs(cur);
//换一种选择方式（循环的下一步），把刚刚的操作撤销
cur.pop_back();
flag[i] = 0;
}
}
}
int main() {
//输入元素个数
cin >> n;
//默认为1到n的顺序排列
for (int i = 0; i < n; i++) {
arr.push_back(i+1);
flag.push_back(0);
}
//刚开始没有元素被选择，定义空数组cur
vector<int> cur;
//递归开始
dfs(cur);
return 0;
}
输入3，则序列为{1,2,3}，得到它的6种全排列：
非递归方式输出排列&下一个字典序
非递归的方式实际上是在求当前序列的下一个字典序，即输出一个只比当前序列大一点的序列。
两个序列的大小比较，是从前到后依次比较两个序列的对应元素，如果当前位置对应元素相同，则继续比较下一个位置，直到第一个元素不同的位置为止，元素值大的序列在字典序中就大于元素值小的序列。
那么大一点指的是，这两个序列之间没有第三个序列可以作为中间值，比如2143就是2134的下一个字典序，其他的排列要么小于2134，要么大于2143。
通过分析可以看到，下一个字典序的求解方法是：
1、先找到当前序列中，最靠右的一个递增子序列中倒数第二个元素m，找不到则说明当前序列已经是字典序的最后一个；
2、再从右往左找到第一个大于m的元素n；
3、交换m和n的值；
4、最后把m之后的序列倒转顺序，就得到了下一个字典序。
上述的调整方式可以用折线图来理解，假设最开始的序列是按顺序的，设为{1,2,3,4,5}，这个序列在坐标系中可以用一条递增的直线来表示，那么字典序的排列就是把这条折线调整成递减的过程，其中的每一个折线，都是上一个折线的最小程度地减小，按照上述的求解方式画画线试试，就理解了什么是最小程度地减小。
代码的功能为：输入序列的长度k，以及每个元素值，输出当前序列之后的所有字典序排列。
int main() {
int k;
//输入序列arr
cin >> k;
vector<int> arr;
for (int i = 0; i < k; i++) {
int num;
cin >> num;
arr.push_back(num);
}
cout << "rest arrays:" << endl;
//找arr后面所有的字典序
while (1) {
int m, n;
//找到m，使得arr[m]<arr[m+1]
for (m = k - 2; m >= 0; m--) {
if (arr[m] < arr[m + 1]) {
break;
}
}
//如果这时m=-1，说明序列已经是递减了，没有下一个字典序，程序结束
if (m < 0) break;
//从后往前找到大于m的第一个元素n
for (n = k - 1; n > m; n--) {
if (arr[n] > arr[m]) {
break;
}
}
//交换m和n两个值
int temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
//把m之后的序列倒序
int i = m + 1;
int j = k - 1;
for (; j > i; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//倒序之后的即为下一个字典序，输出
for (int i = 0; i < k; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
return 0;
}
输入4，输入序列值2 1 4 3，得到后面的字典序：
输入4，输入序列值1 2 3 4，得到后面的字典序，实质就是顺序序列的全排列：
非递归方式输出排列&上一个字典序
知道了如何输出当前序列的下一个字典序之后，可以举一反三推理出上一个字典序。这个问题可以变换成一道编程笔试题：
给定一个整数，将其每个数位上的数字单独取出，再随机排列组合得到一个新的数字集合，比如35412可以得到{12345，23541...}的集合，找出集合中最大的、比
小的数字，也就是只比
小一点的那个组合方式。
分析之后发现这就是求的上一个字典序排列，若
是12345，则集合中没有比它更小的数字，因为它就是字典序的第一个排列。
仿照下一个字典序的求法，可以得到上一个字典序的求解方法是：
1、先找到当前序列中，最靠右的一个递减子序列中倒数第二个元素m，找不到则说明当前序列已经是字典序的最后一个；
2、再从右往左找到第一个小于m的元素n；
3、交换m和n的值；
4、最后把m之后的序列倒转顺序，就得到了上一个字典序。
代码也只需要微小的调整：输入序列的长度k，以及每个元素值，输出当前序列之前的所有字典序排列。
int main() {
int k;
//输入序列arr
cin >> k;
vector<int> arr;
for (int i = 0; i < k; i++) {
int num;
cin >> num;
arr.push_back(num);
}
cout << "rest arrays:" << endl;
//找arr前面所有的字典序
while (1) {
int m, n;
//找到m，使得arr[m]>arr[m+1]
for (m = k - 2; m >= 0; m--) {
if (arr[m] > arr[m + 1]) {
break;
}
}
//如果这时m=-1，说明序列已经是递增了，没有上一个字典序，程序结束
if (m < 0) break;
//从后往前找到小于m的第一个元素n
for (n = k - 1; n > m; n--) {
if (arr[n] < arr[m]) {
break;
}
}
//交换m和n两个值
int temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
//把m之后的序列倒序
int i = m + 1;
int j = k - 1;
for (; j > i; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//倒序之后的即为上一个字典序，输出
for (int i = 0; i < k; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
return 0;
}
如果是那道编程题，只需要求上一个字典序，那么把while循环去掉就好。这个题目也可以先求所有的数字集合，再从集合里找到满足条件的数字，但是这种解法时间复杂度非常高，尤其是数字位数较多的情况下，因为DFS需要遍历每一种可能，所以用这种直接求解上一个字典序的方式比较快速直接。
示例略。
参考博客
1、全排列算法
