www.pudn.com > permrank.rar > permrank.cpp


#include <fstream>
#include <stack>
using namespace std;

struct Object
{
int value;
int index;
operator int(){ return value;}
bool operator>(const Object&amt; oo){ return value>oo.value;}
bool operator<(const Object&amt; oo){ return value<oo.value;}
};

void swap(int &amt;a,int&amt; b);
int Factorial(int n);
bool Find_next(Object ob[],int n,int a[]);
//long Find_index(int a[],int less[],int n);
long Find_index(int a[],int less[],int l,int r);

int main(){
ifstream fin("input.txt");
ofstream fout("output.txt");
int n,i,j;
fin>>n;
int *element=new int[n];
Object *ob=new Object[n];
for (i=0;i<n;i++)
{
fin>>element[i];
ob[i].value=element[i];
ob[i].index=i;
}
int *less=new int[n];//less[i] stores numbers of less than element[i] from 0 to i-1
for(i=0;i<n;i++)
less[i]=0;
for(i=1;i<n;i++)
for(j=0;j<i;j++)
if(element[j]<element[i]) less[i]++;
long num=Find_index(element,less,0,n-1);
fout<<num-1<<'\n';
if(Find_next(ob,n,element))
for (i=0;i<n;i++)
fout<<element[i]<<' ';
else{
for(i=n-1;i>=0;i--)
fout<<element[i]<<' ';
}

return 0;
}

void swap(int &amt;a,int&amt; b){
int temp=a;
a=b;
b=temp;
}

int Factorial(int n){//compute n!
if(n==0) return 1;
return n*Factorial(n-1);
}

bool Find_next(Object ob[],int n,int a[]){
stack<Object> s;
s.push(ob[n-1]);
int min=n+1,i=n-2;
while(i>=0){//O(n),可以使用两重for循环简单实现O(n2)
if(ob[i]>s.top()) { s.push(ob[i]);i--;}
else{
while(!s.empty()&amt;&amt;ob[i]<s.top()) {
if(s.top()<min){
min=s.top();
s.pop();
}
}
break;
}
}
if (s.size()==n) return false;
else{
for(int j=0;j<n;j++)
if(a[j]==min)
swap(a[ob[i].index],a[j]);
for(int k=n;k>ob[i].index+1;k--)//冒泡排序，
for(j=ob[i].index+1;j<k-1;j++)
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
return true;
}
}

/*long Find_index(int a[],int less[],int n){
long num=0;
for(int i=0;i<n;i++)
{
num+=(a[i]-less[i]-1)*Factorial(n-i-1);
}
return num;
//if(l==r) return 1;
//return (a[l]-less[l]-1)*Fibonacci(r-l)+Find_index(a,less,l+1,r);
}*/

long Find_index(int a[],int less[],int l,int r){
if(l==r) return 1;
return (a[l]-less[l]-1)*Factorial(r-l)+Find_index(a,less,l+1,r);
}