查找包含重复字母的单词(排列)的排名
查找包含重复字母的单词(排列)的排名
提问于 2014-03-26 01:33:14
虽然关于这个问题已经有很多帖子了，但我还是发了这篇文章。我不想把它作为答案发布，因为它不起作用。这篇文章的答案(Finding the rank of the Given string in list of all possible permutations with Duplicates)对我不起作用。
所以我尝试了这个(这是我抄袭的代码的汇编，我试图处理重复的代码)。不重复的情况运行良好。记账员生成83863，而不是所需的10743。
(阶乘函数和字母计数器数组'repeats‘工作正常。我没有发帖是为了节省空间。)
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;
}
}回答 6
Stack Overflow用户
回答已采纳
发布于 2014-03-26 02:41:44
注意:这个答案是基于1的排名，通过示例隐含地指定。下面是一些Python，它们至少适用于所提供的两个示例。关键的事实是suffixperms * ctr[y] // ctr[x]是排列的数量，其第一个字母是y的perm的length-(i + 1)后缀。
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版本：
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;
}未排序的排列：
from collections import Counter
def unrankperm(letters, rank):
ctr = Counter()
permcount = 1
for i in range(len(letters)):
x = letters[i]
ctr[x] += 1
permcount = (permcount * (i + 1)) // ctr[x]
# ctr is the histogram of letters
# permcount is the number of distinct perms of letters
perm = []
for i in range(len(letters)):
for x in sorted(ctr.keys()):
# suffixcount is the number of distinct perms that begin with x
suffixcount = permcount * ctr[x] // (len(letters) - i)
if rank <= suffixcount:
perm.append(x)
permcount = suffixcount
ctr[x] -= 1
if ctr[x] == 0:
del ctr[x]
break
rank -= suffixcount
return ''.join(perm)Stack Overflow用户
发布于 2016-12-09 23:46:20
Stack Overflow用户
发布于 2015-04-05 15:15:24
我想说David post (公认的答案)非常酷。然而，我想进一步提高它的速度。内部循环试图找到逆序对，并且对于每个这样的逆序，它试图贡献秩的增量。如果我们在该位置使用有序的映射结构(二叉树或BST)，我们可以简单地从第一个节点(左下角)开始进行有序遍历，直到它到达BST中的当前字符，而不是遍历整个映射(BST)。在C++中，std::map是BST实现的完美选择。下面的代码减少了必要的in循环迭代，并删除了if检查。
long long rankofword(string s)
{
long long rank = 1;
long long suffixPermCount = 1;
map<char, int> m;
int size = s.size();
for (int i = size - 1; i > -1; i--)
{
char x = s[i];
m[x]++;
for (auto it = m.begin(); it != m.find(x); it++)
rank += suffixPermCount * it->second / m[x];
suffixPermCount *= (size - i);
suffixPermCount /= m[x];
}
return rank;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22642151
复制相关文章
相似问题