对于给定的单词，计算可能的字谜数

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!

例如：

对于 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",
    "Whosebug",
  };

  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
       Whosebug => 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;
    }

对于给定的单词，计算可能的字谜数

For a given word calculate the number of possible anagrams

c#

arrays

string

algorithm

anagram