字符串的全排列+去重+栈的出入

本次博客主要针对三个问题进行讲解，第一，是对于任意一个输入序列输出它的全部可能输出，第二，是在所有可能的输出序列中进行去重，第三，则是判断这个输出的序列可不可能是以栈的方式输出的。
一、字符串的全排列，这里主要介绍两种全排列的方法
1.调用库函数进行全排列，这里先上代码

 do{
           vector<int>temp;
           temp=v;
            if(isvalid(vin,temp)){
                for(int i=0;i<v.size();i++){
                   cout<<v[i]<<" ";

                }
                 cout<<endl;
            }
        } 
        while(next_permutation(v.begin(),v.end()));

上面代码中的do部分由于是从某一个具体题目中截取出来的，所以可以不看，直接cout<<v[i]<<endl;输出即可。
这里，主要介绍下库函数中的next_permutation()函数，他是一种逐渐变大的函数，举个例子此时的v容器内的值是123，然后调用这个函数下一个v容器内的就是132，即他是把先前的容器进行排列然后选出只比上个容器大一点的排列组合进行输出。这里有一个注意的地方就是先要把输入的序列进行从小到大排列，以所有输出序列中最小的那个进行初始值再调用next_permutation()才不会出现漏解的情况。

2.第二种方法就是不采用库函数直接利用递归进行全排列

string str;
string temp;
vector<bool> vis;
vector<string>vic;
void dfs(int cnt,int n){
    if(cnt==n) 
    {   //cout<<temp<<endl;
        vic.push_back(temp);
        return; 
    }
    for(int i=0;i<n;i++) {
        if(vis[i]==false)
        { temp.push_back(str[i]);
        vis[i]=true;
        dfs(cnt+1,n);
        vis[i]=false;
        temp.pop_back();
        } 
    }
}
int main(){ 
    getline(cin,str);
    sort(str.begin(),str.end());
    int n=str.size(); 
    vis.resize(n);
    dfs(0,n);
    sort(vic.begin(), vic.end());
    for (int i = 0; i <vic.size();) {
        cout << vic[i] << endl;
        int num = count(vic.begin(), vic.end(), vic[i]);
        i += num;

    }
    system("pause");
    return 0;

}

这里首先定义的全局变量，str是输入的序列，temp是暂时存储某一种输出序列，vis是bool类型的容器用来存储输入序列中每一个元素是否进入输出序列，即vis[i]=true表示该对应元素进入输出序列，vic容器用来存储所有的输出可能即所有全排列，以便进行去重。
这里为了更形象的进行讲解，我以输入序列012为例子进行讲解。
str=012，然后进行排序，n=3，定义一个容量为3的bool容器存储每一个元素的取或不取，初始化时把该容器内所有值定义为false，然后把0和n传去全排列的子函数中，其中参数cnt=0，表示目前输出序列的长度为0，当cnt=n时证明此时所有元素都进入的输出序列就可以把该序列输出了。

i=0，开始循环，vis[0]=false，则temp=0，然后把vis[0]=true表示已经取到了该元素，然后把cnt=1再送入dfs中
temp=0
第二重递归，vis[0]=true不取，vis[1]=false取,然后把vis[1]=true,cnt=2进入dfs中
temp=01
第三重递归，vis[0]=true，vis[1]=true，vis[2]=false取，然后vis[2]=true,cnt=3进入dfs中
temp=012
第四重递归，此时cnt=n了可以直接把temp输出，然后return
返回到第三重，此时for循环进行到i=2，然后vis[2]=false，把最后一个元素弹出，for循环结束
temp=01
返回到第二重循环，此时i=1，vis[1]=false，弹出1，
temp=0
进行第二重循环的i=2，此时vis[2]=false取，然后vis[2]=true，cnt=2进入dfs
temp=02
进入第三重递归，此时只有vis[1]=false取，然后把vis[1]=true，cnt=3进入dfs
temp=021
进入第四重递归此时cnt=n了可以直接把temp输出，然后return
返回到第三重递归，vis[1]=false，弹出1，
temp=02
for循环进入i=2时，vis[2]=true，循环结束，返回上一重，vis[2]=false，弹出2
temp=0
返回第一重，vis[0]=false，弹出0
temp=空
进入i=1的循环vis[1]=false取，然后vis[1]=true，cnt=1进入dfs
temp=1
进入第二重递归，vis[0]=false取，然后vis[0]=true，cnt=2进入dfs
temp=10
进入第三重递归，vis[2]=false取，然后vis[2]=true，cnt=3进入dfs
temp=102
进入第四重递归此时cnt=n了可以直接把temp输出，然后return
返回第三重递归，vis[2]=false，弹出2，循环结束
temp=10
返回第二重递归，vis[0]=false，弹出0，继续循环
temp=1
循环到i=2时，vis[2]=false取，然后vis[2]=true，cnt=2进入dfs
temp=12
进入第三重递归，只有vis[0]=false取，然后vis[0]=true，cnt=3进入dfs
temp=120
进入第四重递归此时cnt=n了可以直接把temp输出，然后return
接下来也是逐一弹出末尾元素然后再进行循环，这里就不重复赘述了，也给读者继续完善以2开头的全排列。

二、去重
由上面所述已经把所有的输出序列装入到vic容器中，接下来要进行去重操作
这里我采用的方法是先将所有的输出序列进行排列，然后进行for循环输出，输出vic[i]后，利用库函数中自带的累加函数，计算该输出序列在所有序列中的个数，然后i+这个个数就可以直接跳过后面的重复序列，实现降重的目的。

三、栈的判断
基于上面所给出的全排列问题与栈进行结合，判断给出一个输入序列，他的所有输出序列中有哪些符合栈的出栈顺序的。

bool isvalid(vector<int>&vin,vector<int>&v){
    stack<int>s;
    reverse(v.begin(), v.end());
    int n=v.size();
    for(int i=0;i<=vin.size();i++){
        s.push(vin[i]);
        while(!s.empty()&&s.top()==v.back()){
            s.pop();
            v.pop_back();
        }
    }
    if(!s.empty())
        return false;
    return true;
}

这里直接先上代码，其中vin存放的输入序列，v存放的是其中某一种输出序列，定义了一个栈，由于要进行逐一比对然后弹出，而vector容器是一头进出的，所以我这里先进行了逆序方便弹出已比对的元素。这里我用一个具体的例子来说明这段代码。
输入序列 5 4 2 1 3 输出序列 1 2 3 4 5
1.定义栈，然后输出序列逆序 5 4 3 2 1
2.将输入序列逐个压栈，5进栈，然后跟容器的末尾元素比较，这里要保证栈非空再比较，5！=1，继续压栈
3.4进栈，4！=1，2进栈，2！=1，1进栈，1==1进入循环弹出比对成功的元素，再进行比对，2==2，弹出，4！=3，3进栈，此时所有输入元素全部进栈了，3==3弹出，4==4弹出，5==5弹出，此时循环结束
4.判断此时栈是否为空，如果栈为空则该输出序列是正常出栈顺序，否则不是出栈顺序。