050320173repeat.cpp

设R={ r , r , , rn 1 2 &#61516 }是要进行排列的n个元素。其中元素n r , r , , r 1 2 &#61516 可能相同。试设计 一个算法

#include <iostream.h>
#include <fstream>
#include <list>
#include <algorithm>
using namespace std;
//#include "time.h"
long int n,countnum=0;
ifstream input;
ofstream output;
void swap(char &a,char &b)
{
	char temp=a;a=b;b=temp;
}
void perm(char a[],int k,int m)
{

	if (k==m)
	{
		for (int i=0;i<=m;i++)
		output<<a[i];
		countnum=countnum+1;
		output<<endl;
	}
	else
	{ 
		list<char> used;
		for (int i=k;i<=m;i++)
		{  
			bool found=false;
			list<char>::iterator pos=find(used.begin(),used.end(),a[i]);
	        if (pos!=used.end()) found=true;
	        if (!found)
			{
			   used.push_back(a[i]);
               swap(a[k],a[i]);
			   perm(a,k+1,m);
		       swap(a[k],a[i]);
			} 
		}
	}
}
int main()
{
	//clock_t start,finish;
	//start=clock();
    input.open("input.txt");
	output.open("output.txt");
    	input>>n;
	char *l=new char[n];
	for (int i=0;i<n;i++)
		input>>l[i];
	perm(l,0,n-1);
	output<<countnum<<endl;
	delete[] l;
	//finish=clock();
	//output<<(double)(finish-start)/CLOCKS_PER_SEC<<" secouds"<<endl;
	return 0;
}