一种粗糙的全排列算法
/*This is a free Program, You can modify or redistribute it under the terms of GNU*Description:给定一个字符串,输出它的全排列, 如给定字符串abc,输出abc,bac,bca,acb,cab,cba共6种序列*Language: C++*Development Environment: VC6.0*Author: Wangzhicheng*E-mail: 2363702560@qq.com*Date: 2012/10/7*/#include <iostream>#include <string>#include <set>#include <algorithm>using namespace std;string s; //要输入的字符串int len; //字符串的长度int cnt=0; //全排列的序列个数const int max=10;set<string>str_array; //存放字符串的集合/*利用异或操作不使用第三个变量交换两个字符此种方法也可以交换两个整数@a,@b:待交换的两个字符*/inline static void swapChar(char &a,char &b) {a=a^b;b=b^a;a=a^b;}/*@str:当前的字符串将字符串当前位置的字符与下一位置的字符互换,从而能够产生新的字符串如果产生新的字符串没有在向量中出现过,则加入向量*/void _FullArrange(string str) {size_t i,j;for(i=0;i<str.size()-1;i++) {for(j=i+1;j<str.size();j++) {if(str[i]!=str[j]) {swapChar(str[i],str[j]);if(str_array.find(str)==str_array.end()) str_array.insert(str);}}}}/*此函数实现全排列,函数首先将原始的字符串加入向量中,然后依次从向量中取数据调用_FullArrange()函数实现全排列*/void FullArrange() {str_array.insert(s);set<string>::iterator it;for(it=str_array.begin();it!=str_array.end();it++) {_FullArrange(*it);}copy(str_array.begin(),str_array.end(),ostream_iterator<string>(cout,"\n"));cnt=str_array.size();cout<<"共有"<<cnt<<"个序列"<<endl;}/*如果字符串长度大于等于max,那么程序在有限时间内,找不到所有的排列原因是此时的set集合变的非常得巨大*/void main() {cout<<"请输入一个字符串:";cin>>s;len=s.length();if(len>=max || len<=0) {cerr<<"字符串长度不合法,程序退出!"<<endl;return;}FullArrange();}
