字符串的所有排列

• 真言

交通发达才能发展，农村修路迫不及待。

• 题目

给出一个函数来输出一个字符串的所有排列。

• 思路

思路很简单，时间复杂度O(n*n)，思路如下（对于还有相同字符的字符串，答案会有重复的，去重就好了）

1. 保存一个空的字符串A，
2. 对给定字符串B的每一个字符
3. 插入A中，出入的位置有n（n为当前字符串A的长度）+1种情况
4. 直至A的长度和B相同时，则输出A

举个例子，如下

给定字符串string=“bhe”

1. 
2. 
   
3. 
   
4. 对于三个字符，答案最多就是6个

• 实验

• 代码

test.cpp

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

// function all orders
void All_orders(string A,string B,string::size_type n,ofstream &f);
// function randstring
string RandString();


// function main
int main()
{

	int i = 0;
	while(i<1)
	{
		ofstream f;
		f.open("txt.txt");
		string test = RandString();
		cout<<"test="<<test<<endl;
		All_orders("",test,0,f);
		f.close();
		i++;
	}

	system("pause");
	return 0;
}



// function all orders
void All_orders(string A,string B,string::size_type n,ofstream &f)
{
	if(n < B.length())
	{	
		string next = A;
		next = B[n] + A;
		All_orders(next,B,n+1,f);
		for(string::size_type i = 1;i < A.length();i++)
		{
			next  = A.substr(0,i)+B[n]+A.substr(i,A.length());
			All_orders(next,B,n+1,f);
		}
		if(A.length()>0)
		{
			next = A + B[n];
			All_orders(next,B,n+1,f);
		}
	}
	else if(n == B.length())
	{
		cout<<A<<" "<<endl;
		f<<A<<endl;
	}
}

// function randstring
string RandString()
{
	int size =  4;
	string result = "";
	for(int i = 0; i<size; i++)
	{
		result = result + (char)( ‘a‘ + rand()%10 );
	}
	return result ;
}

面试题之微软 字符串的所有排列