2

Given a string, find the rank of the string amongst its permutations sorted lexicographically. Note that the characters might be repeated. If the characters are repeated, we need to look at the rank in unique permutations.

Look at the example for more details.

Input : 'aba'

Output : 2

The order permutations with letters 'a', 'a', and 'b' :

aab

aba

baa

I was able to solve for unique characters but not with repeated characters. Can someone help me code this in python?

Thanks

Shaishav Garg
  • 41
  • 2
  • You can start with generating all permutations: https://stackoverflow.com/questions/8306654/finding-all-possible-permutations-of-a-given-string-in-python. Actually, you only have to generate permutations up to the string you're given, provided of course that you do it in alphabetic order. There are faster ways, though ... you can figure it out mathematically. – Jim Mischel Dec 16 '17 at 13:58
  • 1
    You may find [this code](https://codegolf.stackexchange.com/questions/114883/i-give-you-nth-permutation-you-give-me-n/115024#115024) of interest. – PM 2Ring Dec 16 '17 at 19:57

2 Answers2

1
long long int pow_mod(long long int a,long long int b)
{
    long long MOD=1000003;
    if(a == 1)
    return 1;
    long long int x =1 ,y = a;
    while(b>0)
    {
        if(b%2)
        {
            x = (x*y)%MOD;
        }
        y = (y*y)%MOD;
        b = b>>1;
    }
    return x;
}


int Solution::findRank(string A) {
    long long ans=0;
    long long mod=1000003;
    long long  arr[300];
    long long n=A.length();
    long long fact[n];
    fact[0]=1;
    for(int i=1;i<n;i++)
    {
        fact[i]=((fact[i-1]%mod)*(i%mod))%mod; 
    }
    for(long long i=0;i<300;i++)
        arr[i]=0;

    for(long long i=0;i<n;i++)
    {

        arr[A[i]]++;

    }
   // for(long long i=0;i<26;i++)
     //   cout<<arr[i]<<" ";


    for(long long i=0;i<n;i++)
    {

        long long cnt=0;
        long long di=1;


        for(long long j=(A[i]-1);j>=0;j--)
        {
                        cnt+=arr[j];

        }




       // cout<<cnt<<" ";

        for(int j=0;j<300;j++)
        {

            di=(di%mod * fact[arr[j]]%mod)%mod;
        }
        long long a=pow_mod(di,(mod - 2)) % mod;



       // cout<<di<<" ";


        ans=(ans+((cnt*fact[n-i-1])%mod * a )%mod)%mod;


      //  cout<<ans<<" ";
       arr[A[i]]--;


    }
    ++ans;
    return ans%mod;



}
suraj katiyar
  • 9
  • 3
  • While your reply may answer the question, it is better to include the essential parts of the answer here and provide a link for reference. I'd recommend explaining what you have done and how it works. – Karl May 28 '19 at 10:04
0

You could generate the permutations, sort them, and find your original string:

from itertools import permutations
def permutation_index(s):
    return sorted(''.join(x) for x in permutations(s)).index(s)
Mureinik
  • 297,002
  • 52
  • 306
  • 350