用递归的方法来实现强大的全排列功能
输入一行字符串,然后将字符串中的所有字符进行全排列,然后按照从小到大的顺序输出,每个输出占一行。
输入输出示例:
输入数据:
abc
输出数据:
abc
acb
bac
bca
cab
cba
分析:
使用string来保存字符串,便于拆分和分割。使用vector来保存全排列的结果,便于操作和排序。
用户输入一个字符串str,程序的任务是对str求全排列,也就是求
str[0]~str[length-1]的全排列
可以分为先求str的第一个字符str[0],然后求str[1]~str[length-1]的全排列,然后将str[0]分别插入到这些全排列的不同的位置中;
然后求str[1]~str[length-1]的全排列,有可以分成先求str[1],然后求str[2]~str[length-1]的全排列,然后将str[1]插入到不同的位置中;
由此得到递归,
求str[n]~str[length-1]的全排列,分为先求str[n-1]~str[length-1]的全排列,然后将str[n]分别插入到这个全排列的每个结果的所有的位置;
当n = length -1 的时候,找到递归的出口。
通过递归获得str的全排列,然后通过stl中的sort函数,进行排序。
程序代码:
#include
#include
#include
using namespace std;
vector
{
vector
if(str.length()==1) //递归的出口
{
v.push_back(str);
return v;
}
char c = str[0];
string x = str.substr(1);
vector
for(int i=0;i vector v = fun(str); vector for(p=v.begin();p
??