一種粗糙的全排列算法

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