050320170dicorder.cpp

n个元素{1,2,&#61516 , n }有n!个不同的排列。将这n!个排列按字典序排列

#include<iostream.h>
#include<fstream.h>
#include<ctype.h>
#include<string.h>

void Reverse(char*p)
{
    int len=strlen(p),i;
    char temp;
    for(i=0;i<len/2;i++)
    {
        temp=p[i];
        p[i]=p[len-1-i];
        p[len-1-i]=temp;
    }

}

char* AddAnyLongInt(char *p1,char *p2)
{
    int flag=0;//进位标志
    int len1=strlen(p1),len2=strlen(p2),temp,pos,pos1,pos2;
    char *p;
    if(len1>len2)
    {
        temp=len1;
        len1=len2;
        len2=temp;
        char *p0=p1;
        p1=p2;
        p2=p0;
    }
    pos=pos1=pos2=0;
    p=new char[len2+2];
    while(pos<len1)
    {
        temp=(p1[pos1++]-'0')+(p2[pos2++]-'0')+flag;
        if(temp>9)
        {
            flag=1;
            temp-=10;
        }
        else
            flag=0;
        p[pos++]=temp+'0';
    }
    while(pos<len2)
    {
        temp=(p2[pos2++]-'0')+flag;
        if(temp>9)
        {
            flag=1;
            temp-=10;
        }
        else
            flag=0;
        p[pos++]=temp+'0';
    }
    if(flag)
        p[pos++]='1';
    p[pos]='\0';
    
    return p;
}

char *MultiAnyLongInt(char *p1,char *p2)
{
    int main,left;
    int len1=strlen(p1),len2=strlen(p2),pos,pos1,pos2,temp;
    char *p=new char[len1+len2+1];
    main=left=0;
    p[len1+len2]='\0';
    for(pos=0;pos<len1+len2;pos++)
        p[pos]='0';
    for(pos1=0;pos1<len1;pos1++)
    {
        for(pos2=0;pos2<len2;pos2++)
        {
            pos=pos1+pos2;
            temp=(p1[pos1]-'0')*(p2[pos2]-'0')+(p[pos]-'0')+main;
            main=temp/10;
            left=temp%10;
            p[pos]=left+'0';
        }
        p[pos+1]=main+'0';
        main=0;
    }
    pos=len1+len2-1;
    while((pos>=0)&&(p[pos]=='0'))
        pos--;
    pos++;
    p[pos]='\0';
    return p;
}

char * SubAnyLongInt(char *p1,char *p2)
{
    
	int flag=0;
    int len1=strlen(p1),len2=strlen(p2),pos,pos1,pos2,temp;
    char *p;
    p=new char[len1+1];
    p[len1]='\0';
    pos=pos1=pos2=0;
    while(pos<len2)
    {
        temp=(p1[pos1++]-'0')-(p2[pos2++]-'0')-flag;
        if(temp<0)
        {
            flag=1;
            temp+=10;
        }
        else
            flag=0;
        p[pos++]=temp+'0';
    }
    while(pos<len1)
    {
        temp=(p1[pos1++]-'0')-flag;
        if(temp<0)
        {
            flag=1;
            temp+=10;
        }
        else
            flag=0;
        p[pos++]=temp+'0';
    }
    pos--;
    while((p[pos]=='0')&&pos>=0)
        pos--;
    pos++;
    p[pos]='\0';
    return p;
}


char* Factorial(char *p)
{
    
	char *one=new char[2],*pc,*factorial,*temp1,*temp2;
	one="1";
    int len=strlen(p);
	pc=new char[len+1];
	factorial=new char[len+1];
	
	if(len==0)
        return "1";
    strcpy(pc,p);
    strcpy(factorial,p);
	Reverse(pc);
    while(strcmp(pc,one)>0)
    {
		Reverse(pc);
		temp1=SubAnyLongInt(pc,one);
        temp2=MultiAnyLongInt(factorial,temp1);
        delete [] pc;
        pc=temp1;
        delete [] factorial;
        factorial=temp2;
		Reverse(pc);
    }
	delete [] pc;
    return factorial;
}

//convert int to string
char* itos(int n)
{
	int len=0,tmp=n,pos=0;
	while(tmp)
	{
		len++;
		tmp/=10;
	}

	char *p=new char[len+1];
	p[len]='\0';
	while(n)
	{
		tmp=n%10;
		p[pos++]=tmp+'0';
		n/=10;
	}
	return p;
}
		

char* FindDicOrder(int *a,int n)
{
	char* count=new char[1];
	char *temp1,*temp2,*temp3;
	count="";
	int i,j,tmp;
	int MediumNum;
	for(i=0;i<n-1;i++)
	{
		
		MediumNum=a[i]-1;
		
		tmp=0;
		for(j=0;j<i;j++)
		{
			if(a[j]<=MediumNum)
				tmp++;
		}
		MediumNum-=tmp;
		
		temp2=itos(n-1-i);
		
		
		temp1=Factorial(temp2);
		
		
		delete[] temp2;
		temp2=itos(MediumNum);
		
        temp3=MultiAnyLongInt(temp1,temp2);
		
		delete[] temp1,temp2;
		temp1=AddAnyLongInt(count,temp3);
		
		delete[] temp3;
	    delete[] count;
		count=temp1;
	}
	return count;
}



void SearchNext(int *a,int n)
{
	int i,medium=0,tmp,tmp1,tmp2,half;
	for(i=0;i<n-1;i++)
		if(a[i]<a[i+1])
			medium=i+1;
	if(!medium)
		return;
    tmp1=medium-1;
	tmp2=medium;
    while((tmp2<n)&&(a[tmp1]<a[tmp2]))
		tmp2++;
	tmp2--;
	tmp=a[tmp1];
	a[tmp1]=a[tmp2];
	a[tmp2]=tmp;
	half=(medium+n-1)/2;
	for(i=medium;i<=half;i++)
	{
	    n--;
		tmp=a[i];
		a[i]=a[n];
		a[n]=tmp;
	}
	
}

void main()
{
	ifstream fin("input.txt");
	ofstream fout("output.txt");
	int n;
	fin>>n;
	
	int *input=new int[n];
	int i;
    for(i=0;i<n;i++)
		fin>>input[i];
	
	fin.close();

	char* count=FindDicOrder(input,n);
    SearchNext(input,n);
	
	
	Reverse(count);
	if(!strlen(count))
		fout<<0<<endl;
	else
        fout<<count<<endl;
	for(i=0;i<n;i++)
		fout<<input[i]<<" ";
	fout.close();
	
	
	delete[] input,count;
}