查词的排名（排列）有重复的字母 [英] Finding the ranking of a word (permutations) with duplicate letters
问题描述
我张贴这种虽然很多已经张贴了关于这个问题的。我没有要发布的答案，因为它不工作。这个问题的答案职位（<一href="http://stackoverflow.com/questions/17620694/finding-the-rank-of-the-given-string-in-list-of-all-possible-permutations-with-d">Finding在重复）所有可能的排列名单给定字符串的排名并没有为我工作。
所以，我想这（这是code编译我抄袭，我的努力来处理重复）。非重复的情况下正常工作。簿记员产生83863，不是所需10743
（阶乘函数和信计数器阵列'重复'工作正常，我没有张贴，以节省空间。）
而（指针！=长度）
{
如果（sortedWordChars [指针]！= wordArray [指针]）
{
//交换当前字符与后一
焦炭TEMP = sortedWordChars [指针]
sortedWordChars [指针] = sortedWordChars [下一页]
sortedWordChars [下一页] =气温;
接下来++;
//对于每个位置检查有多少留字有重复的，
//并使用逻辑，如果你需要重排ñ东西，如果'一'的东西
//相似排列的数量为n！/一个！
INT克拉=重复[（sortedWordChars [指针] -64）;
//增量排名
如果（克拉→1）{//重复？
的System.out.println（重复+（sortedWordChars [指针] -64））;
//如有任何字符，请使用重复：（N-1）/（次）！
//例如。如果有1个字符被重复两次，
// X *（N-1）！/ 2！
INT股息= getFactorialIter（长度 - 指针 - 1）;
INT除数= getFactorialIter（CT）;
INT现状=股息/除数;
排名+ =现状;
} 其他 {
排名+ = getFactorialIter（长度 - 指针 - 1）;
}
} 其他
{
指针++;
接下来=指针+ 1;
}
}
注：这个答案是基于1的排名，由例如隐含指定。下面是一些Python的作品至少提供两个例子。关键的事实是， suffixperms * CTR [Y] // CTR [X] 是排列的数字，其第一个字母是是 - （I + 1）的后缀烫发
从收藏导入计数器
高清rankperm（烫）：
等级= 1
suffixperms = 1
CTR =计数器（）
因为我在范围内（LEN（烫））：
X =烫发[（（len个（烫发） - 1） - ⅰ）]
CTR [X] + = 1
y的点击率：
如果（Y＆LT; X）：
等级+ =（（suffixperms * CTR [Y]）// CTR [X]）
suffixperms =（（suffixperms *第（i + 1））// CTR [X]）
回报排名
打印（rankperm（'问题'））
打印（rankperm（会计））
Java版本：
公共静态长rankPerm（字符串烫发）{
长等级= 1;
长suffixPermCount = 1;
的java.util.Map＆LT;性格，整数GT; charCounts =
新的java.util.HashMap＆LT;性格，整数GT;（）;
对于（INT I = perm.length（） - 1; I＆GT; -1;我 - ）{
炭X = perm.charAt（ⅰ）;
INT XCOUNT = charCounts.containsKey（X）？ charCounts.get（x）的+ 1：1;
charCounts.put（X，XCOUNT）;
对于（java.util.Map.Entry＆LT;性格，整数GT; E：charCounts.entrySet（））{
如果（e.getKey（）＆其中; x）的{
排名+ = suffixPermCount * e.getValue（）/ XCOUNT;
}
}
suffixPermCount * = perm.length（） - 我;
suffixPermCount / = XCOUNT;
}
返回等级;
}
I'm posting this although much has already been posted about this question. I didn't want to post as an answer since it's not working. The answer to this post (Finding the rank of the Given string in list of all possible permutations with Duplicates) did not work for me.
So I tried this (which is a compilation of code I've plagiarized and my attempt to deal with repetitions). The non-repeating cases work fine. BOOKKEEPER generates 83863, not the desired 10743.
(The factorial function and letter counter array 'repeats' are working correctly. I didn't post to save space.)
while (pointer != length)
{
if (sortedWordChars[pointer] != wordArray[pointer])
{
// Swap the current character with the one after that
char temp = sortedWordChars[pointer];
sortedWordChars[pointer] = sortedWordChars[next];
sortedWordChars[next] = temp;
next++;
//For each position check how many characters left have duplicates,
//and use the logic that if you need to permute n things and if 'a' things
//are similar the number of permutations is n!/a!
int ct = repeats[(sortedWordChars[pointer]-64)];
// Increment the rank
if (ct>1) { //repeats?
System.out.println("repeating " + (sortedWordChars[pointer]-64));
//In case of repetition of any character use: (n-1)!/(times)!
//e.g. if there is 1 character which is repeating twice,
//x* (n-1)!/2!
int dividend = getFactorialIter(length - pointer - 1);
int divisor = getFactorialIter(ct);
int quo = dividend/divisor;
rank += quo;
} else {
rank += getFactorialIter(length - pointer - 1);
}
} else
{
pointer++;
next = pointer + 1;
}
}
Note: this answer is for 1-based rankings, as specified implicitly by example. Here's some Python that works at least for the two examples provided. The key fact is that suffixperms * ctr[y] // ctr[x] is the number of permutations whose first letter is y of the length-(i + 1) suffix of perm.
from collections import Counter
def rankperm(perm):
rank = 1
suffixperms = 1
ctr = Counter()
for i in range(len(perm)):
x = perm[((len(perm) - 1) - i)]
ctr[x] += 1
for y in ctr:
if (y < x):
rank += ((suffixperms * ctr[y]) // ctr[x])
suffixperms = ((suffixperms * (i + 1)) // ctr[x])
return rank
print(rankperm('QUESTION'))
print(rankperm('BOOKKEEPER'))
Java version:
public static long rankPerm(String perm) {
long rank = 1;
long suffixPermCount = 1;
java.util.Map<Character, Integer> charCounts =
new java.util.HashMap<Character, Integer>();
for (int i = perm.length() - 1; i > -1; i--) {
char x = perm.charAt(i);
int xCount = charCounts.containsKey(x) ? charCounts.get(x) + 1 : 1;
charCounts.put(x, xCount);
for (java.util.Map.Entry<Character, Integer> e : charCounts.entrySet()) {
if (e.getKey() < x) {
rank += suffixPermCount * e.getValue() / xCount;
}
}
suffixPermCount *= perm.length() - i;
suffixPermCount /= xCount;
}
return rank;
}
这篇关于查词的排名（排列）有重复的字母的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
