全排列------康托展开

2008-12-05 19:30
vj上的题，求1~n的第m(1<=m<=n!)种全排列。用了康托展开。。。。。。

#include<iostream>
#include<cstring>
using namespace std;

struct BigNum{
       int len,num[200];
       BigNum(){
             len = 1;
             memset(num,0,sizeof(num));
       }
       void Format();
       BigNum(char* str);
       void Inc();
};

void BigNum::Format(){
     for(int i=0;i<len;i++){
         num[i+1] += num[i]/10;
         num[i] %= 10;
     }
     if(num[len]>0) len++;
}
   
BigNum::BigNum(char* str){
      len = strlen(str);
     
      memset(num,0,sizeof(num));
      for(int i=0;i<len;i++)
          num[i] = str[len-i-1] - '0';
}

void BigNum::Inc(){
     num[0]++;
     Format();
}

istream& operator>>(istream& in,BigNum& a){
         char str[100];
        
         in>>str;
         a = str;
        
         return in;
}

BigNum operator*(const BigNum& a,const BigNum& b){
       if(a.num[0]==0&&a.len==1)
          return a;
       if(b.num[0]==0&&b.len==1)
          return b;
   
       int len = a.len + b.len;
       BigNum r;
       int i,j;
      
       for(i=0;i<a.len;i++)
           for(j=0;j<b.len;j++)
               r.num[i+j] += a.num[i]*b.num[j];
      
       while(r.num[len]==0) len--;
       len++;
       r.len = len;
       r.Format();
      
       return r;
}

bool operator==(const BigNum& a,const BigNum& b){
     if(a.len!=b.len) return false;
    
     for(int i=0;i<a.len;i++)
         if(a.num[i]!=b.num[i]) return false;
    
     return true;
}

bool operator<(const BigNum& a,const BigNum& b){
     if(a.len!=b.len) return a.len<b.len;
     if(a==b) return false;
    
     for(int i=a.len-1;i>=0;i--)
         if(a.num[i]!=b.num[i]) return a.num[i] < b.num[i];
}

BigNum operator-(BigNum a,const BigNum& b){
       if(a==b) return BigNum();
         
       int i,j;
      
       for(i=0;i<a.len;i++){
           if(a.num[i]>b.num[i])
              a.num[i] -= b.num[i];
           else{
               a.num[i+1]--;
               a.num[i] += 10;
               a.num[i] -= b.num[i];
           }
       }
      
       a.Format();
       while(a.num[a.len]==0) a.len--;
       a.len++;
      
       return a;
}

BigNum operator/(const BigNum& a,const BigNum& b){
       if(a<b) return BigNum();
      
       BigNum Iter,temp;
       Iter.Inc();
      
       while(b*Iter<a) Iter.Inc();
      
       if(!(b*Iter==a)){
           temp = "1";
           Iter = Iter - temp;
       }
      
       return Iter;
}

BigNum operator%(const BigNum& a,const BigNum& b){
       if(a<b) return a;
       if(a==b) return BigNum();
      
       BigNum div = a/b;
       return a - b*div;
}

ostream& operator<<(ostream& out,const BigNum& a){
         for(int i=a.len-1;i>=0;i--)
             out<<a.num[i];
        
         return out;
}

int main(void){
    BigNum m;
    int n;
    BigNum Fact[30],Iter;
    BigNum cur;
    char str[10];
    int i,j,k,t;
    bool used[30];
   
    cin>>n>>m;
    Iter = "1";
    Fact[1] = "1";
    m = m - Iter;
   
    for(i=2;i<=n;i++,Iter.Inc()){
        Fact[i] = Fact[i-1]*Iter;
    }
   
    memset(used,0,sizeof(used));
    for(i=n;i>1;i--){
        cur = m/Fact[i];//Fact[i] == (i-1)!

        m = m % Fact[i];
       
        cur.Inc();
        k = cur.num[0];
        k += cur.num[1]*10;
       
        t = 0;
        for(j=1;t<k;j++)
            if(!used[j]) t++;
        j--;
       
        cout<<j<<" ";
        used[j] = true;
    }
    for(i=1;i<=n;i++)
        if(!used[i]){
           cout<<i;
           break;
        }
   
    system("pause");
    return 0;
}