全排列---STL方法与递归方法

程序员文章站 2022-06-28 21:54:17

...

1.STL—《algorithm》中的两个函数next_permutation和prev_permutation
- next_permutation:对于当前的排列，如果在字典序中还存在下一个排列，返回真，并且将下一个排列赋予当前排列，如果不存在，就把当前排列进行递增排序。
- prev_permutation对于当前的排列，如果在字典序中还存在前一个排列，返回真，并且将前一个排列赋予当前排列，如果不存在，就把当前排列进行递减排序。
- 那么利用next_permutation可以很轻松的实现全排列。
- 代码:
```
#include <iostream>


#include<algorithm>

using namespace std;

int main(int argc, char *argv[])
{
    string str="2132";
    sort(str.begin(),str.end());
    do{
        cout<<str<<endl;
    }
    while(next_permutation(str.begin(),str.end()));
    return 0;
}
//输出为:
1223
1232
1322
2123
2132
2213
2231
2312
2321
3122
3212
3221
```

2.字符串的字典顺序的全排列

使用去重递归的方法
这里不使用stl的方法，自己使用递归的方法实现函数
考虑我们在求1234的全排列的做法,其做法如下图：也是递归程序的执行过程

全排列---STL方法与递归方法

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string>res;
        if(str.size()==0)return res;
        Permutation(res,str,0);
        sort(res.begin(),res.end());
        return res;
    }
    void Permutation(vector<string>&res,string str,int begin){
        if(begin==str.size()-1)res.push_back(str);
        for(auto i=begin;i<str.size();i++){
            ////有重复字符时，跳过
            if(i!=begin&&str[i]==str[begin])continue;
            //当i==begin时，也要遍历其后面的所有字符；
            ////当i!=begin时，先交换，使第begin位取到不同的可能字符，再遍历后面的字符
            swap(str[i],str[begin]);
            Permutation(res,str,begin+1);
            //为了避免重复的情况，还需要将begin处的元素重新换回来
            swap(str[i],str[begin]);
        }
    }
};