有重复元素的排列问题.cpp

递归和分治法解一系列经典算法

#include<iostream.h>
#include<fstream.h>
template<class T>

void Swap(T &a,T &b)
{
	T temp;
	temp=a;
	a=b;
	b=temp;
	
}
template<class T>
bool Search(T *list, T x, int begin, int end)
{
	for(int i=begin;i<=end;i++)
		if(list[i]==x)return 1;
		return 0;
}
template<class T>
void Perm(T list[],int k,int m,unsigned int &count,ofstream &outfile)
{
	if(k==m)
	{
		for(int i=0;i<=m;i++){
			outfile<<list[i];
			cout<<list[i];
		}
        count++;
		outfile<<endl;
		cout<<endl;
	}
	else
		for(int i=k;i<=m;i++)
		{
			if(i==k||!Search(list,list[i],k,i-1))
			{
				Swap(list[k],list[i]);
				Perm(list,k+1,m,count,outfile);
				Swap(list[k],list[i]);
			}
		}
}
void main()
{
	int n;
	ifstream infile("input.txt");
	if(!infile){
		cout<<"Can't open input.txt!"<<'\n';
		return;
	}
	
	ofstream outfile("output.txt");
	if(!outfile){
		cout<<"Can't open output.txt!"<<'\n';
		return;
	}
	
	infile>>n;
	char *e=new char[n];
	for(int i=0;i<n;i++)infile>>e[i]; 
	unsigned int count=0;
	Perm(e,0,n-1,count,outfile);
	outfile<<count<<endl;
	cout<<count<<endl;
	delete []e;
	
	infile.close();
	outfile.close();
}