uva 153 - Permalex

Permalex

Given a string of characters, we can permute the individual characters to make new strings. If we can impose an ordering on the characters (say alphabetic sequence), then the strings themselves can be ordered and any given permutation can be given a unique number designating its position in that ordering. For example the string `acab' gives rise to the following 12 distinct permutations:



Thus the string `acab' can be characterised in this sequence as 5.

Write a program that will read in a string and determine its position in the ordered sequence of permutations of its constituent characters. Note that numbers of permutations can get very large; however we guarantee that no string will be given whose position is more than  .

Input and Output

Input will consist of a series of lines, each line containing one string. Each string will consist of up to 30 lower case letters, not necessarily distinct. The file will be terminated by a line consisting of a single #.

Output will consist of a series of lines, one for each line of the input. Each line will consist of the position of the string in its sequence, right justified in a field of width 10.

Sample input

bacaa
abc
cba
#

Sample output

        15
         1
         6

permutation 

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

string S;
vector<int>prime;
int base[50],cur[50];
int notp[30];

void getP(){
    notp[0]=notp[1]=1;
    int b;
    rep(i,30)
        if(!notp[i]){
            prime.push_back(i);
            if(DBG)printf("%d\n",i);
            for(int b=i*2;b<30;b+=i)notp[b]=1;
        }
}
void getEle(int c){
    int a;
    REP(i,2,c+1){
        a=i;
        rep(j,prime.size()){
            while(a%prime[j]==0)a/=prime[j],base[prime[j]]++;
            if(a==1)break;
        }
    }
}
void getCur(int c){
    int a;
    REP(i,2,c+1){
        a=i;
        rep(j,prime.size()){
            while(a%prime[j]==0){
                a/=prime[j];
                if(base[prime[j]])base[prime[j]]--;
                else cur[prime[j]]++;
            }
            if(a==1)break;
        }
    }
}
int getN(string s,int a,int b){
    int cnt[26];
    memset(cnt,0,sizeof(cnt));
    memset(cur,0,sizeof(cur));
    REP(i,a,b)cnt[s[i]-'a']++;
    rep(i,26)if(cnt[i]>1)getEle(cnt[i]);
    getCur(b-a);
    int c=1;
    REP(i,2,32)if(cur[i])c*=int(pow(i,cur[i])+0.5);
    if(DBG)printf("getN: %s\n",s.c_str());
    return c;
}
void getNum(){
    int c=0;
    char d;
    bool add[256];
    string s;
    rep(i,S.size()-1){
        memset(add,0,sizeof(add));
        REP(j,i+1,S.size())
            if(S[j]<S[i]&&!add[S[j]]){
                s=S;
                add[s[j]]=1;
                d=s[i],s[i]=s[j],s[j]=d;
                c+=getN(s,i+1,s.size());
            }
    }
    printf("%10d\n",c+1);
}
int main(){
    getP();
    while(cin>>S){
        if(S[0]=='#')break;
        getNum();
    }
}