字符串排列排名+数据结构

Question

手头的问题是:

给出一个字符串.在按字典顺序排列的所有排列中列出其排名.

这个问题可以用数学方法尝试,但我想知道是否还有其他一些算法来计算它？

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

编辑

感谢排列生成部分的详细解答,有人还可以提出一个好的数据结构吗？我只能想到树木.

Answer 1

存在O(n |Σ|)算法以在其排列列表中找到长度为n的字符串的等级.这里,Σ是字母表.

算法

排在s以下的每个排列都可以以pcx的形式唯一地写出; 哪里:

• p是s的正确前缀
• Ç是排名刚过出现的字符下一个字符p的小号.和Ç也是的部分发生的字符小号不包括在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;
}