String permutations rank + data structure

algorithm, data-structures, permutation, string

Solution

There is an O(n|Σ|) algorithm to find the rank of a string of length n in the list of its permutations. Here, Σ is the alphabet.

Algorithm

Every permutation which is ranked below s can be written uniquely in the form pcx; where:

- p is a proper prefix of s

- c is a character ranked below the character appearing just after p in s. And c is also a character occurring in the part of s not included in p.

- x is any permutation of the remaining characters occurring in s; i.e. not included in p or c.

We can count the permutations included in each of these classes by iterating through each prefix of s in increasing order of length, while maintaining the frequency of the characters appearing in the remaining part of s, as well as the number of permutations x represents. The details are left to the reader.

This is assuming the arithmetic operations involved take constant time; which it wont; since the numbers involved can have nlog|Σ| digits. With this consideration, the algorithm will run in O(n2 log|Σ| log(nlog|Σ|)). Since we can add, subtract, multiply and divide two d-digit numbers in O(dlogd).

C++ Implementation

typedef long long int lli;

lli rank(string s){
    int n = s.length();

    vector<lli> factorial(n+1,1);
    for(int i = 1; i <= n; i++)
        factorial[i] = i * factorial[i-1];
    
    vector<int> freq(26);
    lli den = 1;
    lli ret = 0;
    for(int i = n-1; i >= 0; i--){
        int si = s[i]-'a';
        freq[si]++;
        den *= freq[si];
        for(int c = 0; c < si; c++) 
            if(freq[c] > 0) 
                ret += factorial[n-i-1] / (den / freq[c]);
    }
    return ret + 1;
}

Problem

The problem at hand is: Given a string. Tell its rank among all its permutations sorted lexicographically. The question can be attempted mathematically, but I was wondering if there was some other algorithmic method to calculate it ? Also if we have to store all the string permutations rankwise , how can we generate them efficiently (and what would be the complexity) . What would be a good data structure for storing the permutations and which is also efficient for retrieval? EDIT Thanks for the detailed answers on the permutations generation part, could someone also suggest a good data structure? I have only been able to think of trie tree.

Original source