字符串排列秩+数据结构

Question

手头的问题是:

Given a string. Tell its rank among all its permutations sorted lexicographically.

这个问题可以从数学上尝试，但我想知道是否有其他算法方法可以计算它？

此外，如果我们必须按顺序存储所有字符串排列，我们如何有效地生成它们(以及复杂性)。什么是用于存储排列的好的数据结构并且对于检索也很有效？

编辑

感谢排列生成部分的详细解答，有人可以推荐一个好的数据结构吗？我只能想到特里树。

Answer 1

有一个复杂度为 O(n|Σ|) 的算法来查找长度为 n 的字符串在其排列列表中的排名。这里，Σ 是字母表。

算法

s以下的每个排列都可以唯一写成pcx的形式；其中:

• p 是s
的专有前缀
• c 是在 s 中排在 p 之后的字符之下的字符。而c也是出现在s部分的字符，不属于p。
• x 是 s 中剩余字符的任意排列；即不包含在 p 或 c 中。

我们可以通过按长度递增顺序遍历 s 的每个前缀来计算每个类中包含的排列，同时保持字符出现在 剩余部分中的频率s，以及x代表的排列数。细节留给读者。

这是假设所涉及的算术运算需要常数时间；它不会；因为涉及的数字可以有 nlog|Σ|数字。考虑到这一点，该算法将在 O(n² log|Σ| log(nlog|Σ|)) 中运行。因为我们可以在 O(dlogd) 中对两个 d 位数进行加减乘除。

C++实现

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;
}