Tuesday, March 22, 2016

Lexicographic Rank of a String

public class LexicographicRank
{
    public static void main(String args[])
    {
        String str = "dcba";
        int n = str.length();
        int rank = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int x = 0;
            for (int j = i + 1; j < n; j++)
            {
                if (str.charAt(i) > str.charAt(j))
                    x++;
            }
            rank = rank + (x * (fact(n - i - 1)));
        }
        System.out.println(rank + 1);
    }
   
    private static int fact(int n)
    {
        int res = 1;
        if (n == 0)
            return 1;
        else
        {
            for (int i = 1; i <= n; i++)
            {
                res = res * i;
            }
        }
        return res;
    }
}

No comments:

Post a Comment