一种粗糙的全排列算法

/*
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: [email protected]
*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();
}