For a given word calculate the number of possible anagrams

user_17693898 0
Viewed 85

For a given word calculate the number of possible anagrams. The resulting words do not have to exist in the dictionary. Anagrams do not have to be repeated and anagrams do not have to be generated, only their number calculated.

The last test is not working and I do not know how should I make it work. Can you help me, please?

Here is my code:

    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"

The submitted solution does not correctly calculate the number of unique anagrams if there are repeating letters.

anagram arrays algorithm string c#
1 Answers

If you have word of length n with m distinct letters w1, ..., wm where wi is occurence of ith letter, the number of possible anagrams is

Math:

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

For instance:

  1. For abc we have n = 3, m = 3, w1 = w2 = w3 = 1:
N = 3! / 1! / 1! / 1! = 6 / 1 / 1 / 1 = 6
  1. For aaab we have n = 4, m = 2, w1 = 3, w2 = 1:
N = 4! / 3! / 1! = 24 / 6 / 1 = 4

Code:

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()));
}

Demo: (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);

Outcome:

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

Edit: If you are not allowed to use System.Numerics and System.Linq you can try using 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;
    }
user_23194070
Related