手头的问题是:
给定一个字符串。告诉它在按字典顺序排序的所有排列中的排名。
这个问题可以在数学上尝试,但我想知道是否有其他算法方法来计算它?
此外,如果我们必须按等级存储所有字符串排列,我们如何有效地生成它们(以及复杂性是多少)。什么是存储排列的好数据结构并且对于检索也是有效的?
编辑
感谢您对排列生成部分的详细回答,有人还可以建议一个好的数据结构吗?我只能想到特里树。
手头的问题是:
给定一个字符串。告诉它在按字典顺序排序的所有排列中的排名。
这个问题可以在数学上尝试,但我想知道是否有其他算法方法来计算它?
此外,如果我们必须按等级存储所有字符串排列,我们如何有效地生成它们(以及复杂性是多少)。什么是存储排列的好数据结构并且对于检索也是有效的?
编辑
感谢您对排列生成部分的详细回答,有人还可以建议一个好的数据结构吗?我只能想到特里树。
有一个 O(n|Σ|) 算法可以找到长度为 n 的字符串在其排列列表中的排名。这里,Σ 是字母表。
每个排在s以下的排列都可以唯一地写成pcx形式;在哪里:
我们可以通过以长度递增的顺序遍历s的每个前缀来计算每个类中包含的排列,同时保持字符出现在s的其余部分的频率以及x表示的排列数量。细节留给读者。
这是假设所涉及的算术运算需要恒定时间;它不会;因为所涉及的数字可以有 nlog|Σ| 位数。考虑到这一点,算法将在 O(n 2 log|Σ| log(nlog|Σ|)) 中运行。因为我们可以在 O(dlogd) 中对两个 d 位数字进行加减乘除。
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;
}
这类似于快速选择算法。在一个未排序的整数数组中,找到某个特定数组元素的索引。分区元素将是给定的字符串。
编辑:
实际上它类似于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。
给定一个字符串,找出它在按字典顺序排序的所有排列中的排名。例如,“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