求助：含重复字母的单词下字母变位词位置计算代码失效问题

阿华AIGC实验室

2026-4-30

解决含重复字母的单词排列位置计算问题

嘿，我完全懂你卡壳的点——你的代码在处理无重复字母的单词（比如car）时工作正常，但遇到像test、bookkeeper这类有重复字母的单词就失效了，核心问题出在排列数的计算没有考虑重复字母的去重。

问题根源分析

当单词里有重复字母时，比如caar，如果单纯用math.factorial(len(wlsort)-1)来计算以某个字母开头的排列数，会把重复的排列（比如交换两个a的位置）算成不同的情况，但实际上这些是同一个单词，所以需要对阶乘结果进行去重修正。

举个例子：caar剩余字母是['c','a','a','r']，当计算以第一个a开头的排列数时，剩下的字母是['c','a','r']，这时候排列数是3!没问题；但如果剩余字母是['a','a','c','r']，计算以c开头的排列数时，剩下的字母是['a','a','r']，实际唯一排列数应该是3!/(2!)，而不是3!——因为两个a交换位置不会产生新单词。

解决思路与修改方案

我们需要做的是：

维护剩余字母的频率统计，而不是单纯排序后遍历，这样能准确计算重复字母的数量。
对于每个当前字符，遍历所有比它小的唯一字符，计算以该字符开头的唯一排列数，公式为：
```
(剩余长度-1)! / (乘积：每个重复字母的出现次数的阶乘)
```
累加这些排列数，然后移除当前字符，继续处理剩余单词。

下面是修改后的代码示例：

import math
from collections import Counter

def listPosition(word):
    count = 0
    chars = list(word)
    char_counts = Counter(chars)
    
    while chars:
        current_char = chars[0]
        # 遍历所有比当前字符小的唯一字符
        for c in sorted(char_counts.keys()):
            if c >= current_char:
                break
            # 临时复制计数器，减去当前要计算的字符c一次
            temp_counts = char_counts.copy()
            temp_counts[c] -= 1
            if temp_counts[c] == 0:
                del temp_counts[c]
            # 计算分子：(剩余长度-1)!
            numerator = math.factorial(len(chars)-1)
            # 计算分母：各重复字母的阶乘乘积
            denominator = 1
            for freq in temp_counts.values():
                denominator *= math.factorial(freq)
            # 累加唯一排列数
            count += numerator // denominator
        
        # 移除当前字符，更新计数器
        char_counts[current_char] -= 1
        if char_counts[current_char] == 0:
            del char_counts[current_char]
        chars.pop(0)
    
    return count + 1