C#如何计算给定字符串的不同变位词总数量

计算原理 #

含重复字符的变位词计数直接用多重集排列公式即可，逻辑非常明确：

• 先算字符串长度的阶乘，这是所有字符全排列的总数量
• 统计每个字符的出现次数，把每个次数的阶乘乘起来，这个值用来去掉重复字符互换位置生成的相同排列
• 最终结果 = 总长度阶乘 / 各字符出现次数阶乘的乘积

对应给出的两个预期结果验证：

输入aabv：长度4，4! = 24；a重复2次、b和v各出现1次，重复项乘积为2!×1!×1! = 2；24/2=12，和预期一致。
输入aaab：长度4，4! =24；a重复3次、b出现1次，重复项乘积为3!×1! =6；24/6=4，和预期一致。

原有代码问题 #

贴出的代码逻辑完全不匹配计算规则：

• 阶乘计算错误：循环里每次都把计数变量重置为1，每次循环只做了一次乘以(长度-1)的运算，根本没有实现阶乘的逐次累乘
• 完全没有做字符频次统计，没有剔除重复排列的无效计数，不可能得到正确结果。

正确C#实现 #

using System;
using System.Collections.Generic;

public static class AnagramTool
{
    // 阶乘计算辅助方法
    private static long CalcFactorial(int number)
    {
        long res = 1;
        for (int i = 2; i <= number; i++)
        {
            res *= i;
        }
        return res;
    }

    public static long CountUniqueAnagrams(string word)
    {
        if (string.IsNullOrWhiteSpace(word)) return 0;
        
        // 统计每个字符的出现次数
        Dictionary<char, int> charFrequency = new Dictionary<char, int>();
        foreach (char c in word)
        {
            if (charFrequency.ContainsKey(c))
                charFrequency[c]++;
            else
                charFrequency[c] = 1;
        }

        long total = CalcFactorial(word.Length);
        // 除去重复排列的数量
        foreach (int freq in charFrequency.Values)
        {
            total /= CalcFactorial(freq);
        }

        return total;
    }

    // 测试入口
    public static void Main()
    {
        Console.WriteLine(CountUniqueAnagrams("aabv")); // 输出12
        Console.WriteLine(CountUniqueAnagrams("aaab")); // 输出4
    }
}

注：这里用long类型存结果是为了避免稍长的字符串计算阶乘时超出int的取值上限，处理短单词时也可以换成int类型。

内容的提问来源于stack exchange，提问作者Skike