c# - 对于给定的单词，计算可能的字谜词的数量

Question

对于给定的单词，计算可能的字谜词的数量。 生成的单词不一定存在于字典中。 字谜词不必重复，也不必生成字谜词，只需计算它们的数量即可。

最后的测试不起作用，我不知道该如何让它起作用。你能帮我一下吗？

这是我的代码:

    using System;

    static void Main(string[] args)
    {
        string word = Console.ReadLine();
        int wordLenth = word.Length;
        int sameLetter = 1;

        for (int i=0;i<wordLenth;i++)
        {
            for (int j=i+1;j<wordLenth;j++)
            {
                if (word[i]==word[j])
                {
                    sameLetter++;
                }
            }
        }
        int firstResult=1, secondResult=1, lastResult;
        for (int i=1; i <= wordLenth; i++)
        {
            firstResult *= i;
        }
        for (int i = 1; i <= sameLetter; i++)
        {
            secondResult *= i;
        }
        lastResult = firstResult / secondResult;
        Console.WriteLine(lastResult);     
    }

Results:

Compilation successfully executed.
Test 1: Correctly calculate the number of anagrams for "abc" - successful
Test 2: Correctly calculate the number of anagrams for "abc" - success
Test 3: Correctly calculates the number of anagrams for "aaab" - failed
Expected results: "4"
Results obtained: "1"

如果存在重复字母，提交的解决方案无法正确计算唯一字谜词的数量。

Answer 1

如果您的单词长度为 n，其中包含 m 个不同的字母 w1, ..., wm，其中 wi 是第 i 个字母的出现， 可能的字谜数是

数学:

N = n! / w1! / w2! / ... / wm!

例如:

1. 对于 abc，我们有 n = 3、m = 3、w1 = w2 = w3 = 1 :

N = 3! / 1! / 1! / 1! = 6 / 1 / 1 / 1 = 6

对于 aaab，我们有 n = 4、m = 2、w1 = 3、w2 = 1 :

N = 4! / 3! / 1! = 24 / 6 / 1 = 4

代码:

using System.Linq;
using System.Numerics;

...

private static BigInteger Factorial(int value) {
  BigInteger result = 1;

  for (int i = 2; i <= value; ++i)
    result *= i;

  return result;
}

private static BigInteger CountAnagrams(string value) {
  if (string.IsNullOrEmpty(value))
    return 1;

  return value
    .GroupBy(c => c)
    .Aggregate(Factorial(value.Length), (s, group) => s / Factorial(group.Count()));
}

演示: ( Fiddle )

  string[] tests = new string[] {
    "a",
    "aaa",
    "abc",
    "aaab",
    "abracadabra",
    "stackoverflow",
  };

  string report = string.Join(Environment.NewLine, tests
    .Select(test => $"{test,20} => {CountAnagrams(test)}"));

  Console.Write(report);

结果:

                   a => 1
                 aaa => 1
                 abc => 6
                aaab => 4
         abracadabra => 83160
       stackoverflow => 3113510400

编辑:如果您不允许使用System.Numerics和System.Linq，您可以尝试使用long:

    private static long Factorial(int value)
    {
        long result = 1;

        for (int i = 2; i <= value; ++i)
            result *= i;

        return result;
    }

    private static long CountAnagrams(string value)
    {
        if (string.IsNullOrEmpty(value))
            return 1L;
        
        Dictionary<char, int> groups = new Dictionary<char, int>();

        foreach (var c in value)
            if (groups.TryGetValue(c, out int v))
                groups[c] += 1;
            else
                groups.Add(c, 1);
        
        long result = Factorial(value.Length);
        
        foreach (int v in groups.Values)
            result /= Factorial(v);
        
        return result;
    }