查找带有重复字母的单词(排列)的排名

我已经发布了此内容,尽管有关此问题的信息已经很多。我不想发布答案,因为它无法正常工作。

因此,我尝试了一下(这是我抄袭的代码的汇编,也是我尝试处理重复代码的尝试)。非重复案例可以正常工作。BOOKKEEPER生成83863,而不是所需的10743。

(阶乘函数和字母计数器数组“重复”正常工作。我没有张贴此文件以节省空间。)

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;

}

}

回答:

注意:此答案适用于基于1的排名,如示例中所隐含指定。这是一些至少可用于所提供的两个示例的Python。关键事实是suffixperms * ctr[y]// ctr[x]排列的数量,其首字母为y(i + 1)后缀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版本:

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)

以上是 查找带有重复字母的单词(排列)的排名 的全部内容, 来源链接: utcz.com/qa/426315.html

回到顶部