使用栈数据结构进行全排序

全排序书上用的是嵌套+还原的方法进行。这是类似深度搜索的方法，我记得在专门说深度搜索（迷宫问题）时，有两种：嵌套或栈方法。那全排序是否也可以用栈的方法?
2022年11月20日09:31:38

1. 全排序方法1：嵌套+还原 = 深度优先搜索

这是最多的方法。

/*c++ 任务：输出123的全排列*/
#include
#include 
using namespace std;int card[3] = { 1,1,1 };
int box[3] = { 0 };
int dfs(int step) {if (step == 3) { for (int j = 0; j < 3; j++) {std::cout << box[j] << " ";}std::cout << std::endl;return 0;}for (int i = 0; i < 3; i++) {if (card[i] == 1) {box[step] = i+1; // put incard[i] = 0;dfs(step + 1);card[i] = 1; // 这里可以吧 两个变量均还原}}
}int main() {dfs(0);
}

2. 全排序方法2：深度优先搜索 - 使用栈

区别：迷宫不一定有路径，是真的搜索。全排列要给个初始解，不是真正意义上的搜索，更像是深度优先排列。这里的方法主要参考.
算法思路： 先将1 - n依次压入栈中，这是第一组排列，输出；接着循环while(!st.isEmpty()) 每次弹出栈顶元素，然后找在栈外的数有没有比弹出的这个数更大的，如果有那个将这个大的数压入栈中，接着从1-n查找不在栈中的数，依次压入栈中，一次排列输出，结束。
详细步骤：

1. 按照一定的顺序进行搜索，先从简单的1,2,3 作为初始解开始搜索，到3,2，1这样的结束（while 循环结束）
   第一次：（1，2）3出栈，（1）3出栈，2出栈，（1，3入栈）2，（1，3，2入栈）； out->1 3 2
   第二次：(1，3) 2出栈， （1）2出栈，3出栈，（）2出栈，3出栈，1出栈；（2入栈）3，1 （2，1入栈）3 （2，1，3入栈） ；out->2 1 3
   第三次：(2，1)3出栈 （2）3出栈，1出栈 （2，3入栈）1 （2，3，1入栈）；out->2 3 1；
   …

总结：算法主旨：数值从小到大，将靠后的位数放上稍微大的值，后面的数从小到大按顺序放就好。
缺点：好像必须要从1,2，3开始，要是从中间某个排列开始就会失效。
代码：参考中的是Java，这里用c++写，但是发现“无法查找stack类型中是否存在某个值”，所以只能用vector了

/*c++ 任务：输出123的全排列*/
int main() {vector  pointStack;pointStack.push_back(1);pointStack.push_back(2);pointStack.push_back(3);int i = 0;int len_ = pointStack.size();while(pointStack.size() != 0) { // 当为321的时候，此条件才成立vector temp[3];i = pointStack.back();pointStack.pop_back();for (; i < 3; i++) {// 当一个比i大的数不在栈中时候if (std::find(pointStack.begin(), pointStack.end(), i + 1) == pointStack.end()) {pointStack.push_back(i + 1);//将大于弹出的这个数入栈//接着将未入栈的从小到大依次入栈for (int j = 1; j <= 3; j++) {if (std::find(pointStack.begin(), pointStack.end(), j) == pointStack.end())pointStack.push_back(j);}for (auto t_ : pointStack) {cout << t_ << " ";}cout << endl;}}}
}