字符串全排列生成算法

全排列生成算法很多，常见的如字典序，递归等。本文使用的算法是基于递归的，算法如下：

#include<iostream>
           

#include<string>
#include<map>
using namespace std;
map<string ,int> elements;//用于存储要输入的前缀
void permutation(string prefix, string str) 
{

	size_t n = str.length();
    if (n == 0)
	 {
		elements[prefix]=1;
	 }
    else
	{
		for(int i = 0;i<n;i++)
		{
			permutation(prefix+str.at(i), str.substr(0, i)+str.substr(i+1, n));
		}
	}
      
				
}

int main()
{
  string s;
  int m=0;
  getline(cin,s);
  //cout<<s;
  //string::iterator it=s.begin();
  while(s!="exit")
  {
	 permutation("  ",s);
	 map<string ,int>::iterator map_it=elements.begin();
	 while(map_it!=elements.end())
	 {
         cout<<map_it->first<<" "<<map_it->second<<endl;
		 ++map_it;
		 m++;
	 }
	 cout<<"The sum number: "<<m<<endl;
	 //清空计数器，及字符串
	 m=0;
     s="";
     //erase map
	 elements.erase(elements.begin(),elements.end());
     //准备接收下一个字符串。
	 getline(cin,s);
  }
  cout<<m<<endl;

}
           

有一个问题需要注意：字符串中可能有重复的字符，这时只需输出不重复的排列，本文利用的方法是把需要输出的字符串排列先插入到一个map中，然后从map中输出元素，避免了重复。