12

手头的问题是：

给定一个字符串。告诉它在按字典顺序排序的所有排列中的排名。

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

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

编辑

感谢您对排列生成部分的详细回答，有人还可以建议一个好的数据结构吗？我只能想到特里树。

4

3 回答 3

6

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

算法

每个排在s以下的排列都可以唯一地写成pcx形式；在哪里：

  • p是s的适当前缀
  • c是排名低于s中p之后出现的字符的字符。并且c也是出现在s中不包含在p中的部分中的字符。
  • x是s中出现的剩余字符的任何排列；即不包括在p或c中。

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

这是假设所涉及的算术运算需要恒定时间；它不会；因为所涉及的数字可以有 nlog|Σ| 位数。考虑到这一点，算法将在 O(n 2 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;
}
于 2012-07-14T15:07:17.000 回答
4

这类似于快速选择算法。在一个未排序的整数数组中，找到某个特定数组元素的索引。分区元素将是给定的字符串。

编辑：

实际上它类似于QuickSort中的分区方法。给定的字符串是分区元素。一旦生成了所有排列，找到长度为 k 的字符串的秩的复杂度将是 O(nk)。您可以使用递归生成字符串排列并将它们存储在链表中。您可以将此链表传递给分区方法。

这是生成所有字符串排列的java代码：

 private static int generateStringPermutations(String name,int currIndex) {

        int sum = 0;

        for(int j=name.length()-1;j>=0;j--) {
            for(int i=j-1;((i<j) && (i>currIndex));i--) {

                String swappedString = swapCharsInString(name,i,j);
                list.add(swappedString);
                //System.out.println(swappedString);
                sum++;
                sum = sum + generateStringPermutations(swappedString,i);
            }
        }
        return sum;


    }

编辑：

生成所有排列的成本很高。如果字符串包含不同的字符，则可以在不生成所有排列的情况下确定排名。这是链接。

这可以针对有重复字符的情况进行扩展。

而不是 x * (n-1)！这是针对链接中提到的不同情况，

对于重复字符，它将是：

如果有 1 个字符重复两次，

x* (n-1)!/2!

让我们举个例子。对于字符串 abca，组合为：

aabc,aacb,abac,abca,acab,acba,baac,baca, bcaa ,caab, caba ,cbaa （按排序顺序）

总组合 = 4!/2! = 12

如果我们想找到'bcaa'的等级，那么我们知道所有以'a'开头的字符串都在3之前！= 6。

请注意，因为 'a' 是起始字符，所以其余字符是 a,b,c 并且没有重复，所以它是 3!。我们也知道以 'ba' 开头的字符串会在 2 之前！= 2 所以它的等级是 9。

另一个例子。如果我们想找到'caba'的等级：

所有以 a 开头的字符串都是 before = 6。所有以 b 开头的字符串都是 before = 3!/2! = 3（因为一旦我们选择 b，我们就剩下 a,a,c 并且因为有重复，所以它是 3!/2!。所有以 caa 开头的字符串都在 1 之前

所以最终排名是 11。

于 2012-07-14T10:04:07.897 回答
1

来自GeeksforGeeks：

给定一个字符串，找出它在按字典顺序排序的所有排列中的排名。例如，“abc”的等级为 1，“acb”的等级为 2，“cba”的等级为 6。

为简单起见，让我们假设字符串不包含任何重复的字符。

一种简单的解决方案是将 rank 初始化为 1，按字典顺序生成所有排列。生成排列后，检查生成的排列是否与给定的字符串相同，如果相同，则返回排名，如果不是，则将排名加 1。此解决方案的时间复杂度在最坏情况下将是指数级的。以下是一个有效的解决方案。

让给定的字符串为“STRING”。在输入字符串中，'S' 是第一个字符。共有 6 个字符，其中 4 个小于“S”。所以可以有4 * 5！第一个字符小于“S”的较小字符串，如下所示

RXXXXXXXXXXXNXXXXXGXX XXX

现在让我们修复 S' 并找到以 'S' 开头的较小字符串。

对 T 重复同样的过程，rank 是 4*5！+ 4 * 4！+…</p>

现在修复 T 并对 R 重复相同的过程，秩为 4*5！+ 4 * 4！+ 3 * 3！+…</p>

现在修复 R 并为 I 重复相同的过程，等级为 4*5！+ 4 * 4！+ 3 * 3！+ 1*2！+…</p>

现在修复 I 并对 N 重复相同的过程，等级为 4*5！+ 4 * 4！+ 3 * 3！+ 1*2！+ 1 * 1！+…</p>

现在固定 N 并对 G 重复相同的过程，秩为 4*5！+ 4 * 4 + 3 * 3！+ 1*2！+ 1 * 1！+ 0 * 0！

排名 = 4 * 5！+ 4 * 4！+ 3 * 3！+ 1*2！+ 1 * 1！+ 0 * 0！= 597

由于rank的值是从1开始的，所以最终的rank = 1 + 597 = 598

于 2013-02-14T21:37:10.647 回答