functionloopsanagram

C# How to count how many anagrams are in a given string


I have to calculate how many anagrams are in a given word. I have tried using factorial, permutations and using the posibilities for each letter in the word. This is what I have done.

static int DoAnagrams(string a, int x)
{
    int anagrams = 1;
    int result = 0;
    x = a.Length;
    for (int i = 0; i < x; i++)
    { anagrams *= (x - 1); result += anagrams; anagrams = 1; }
    return result;
}

Example: for aabv I have to get 12; for aaab I have to get 4


Solution

  • Answer with Code

    This is written in c#, so it may not apply to the language you desire, but you didn't specify a language.

    This works by getting every possible permutation of the string, adding every copy found in the list to another list, then removing those copies from the original list. After that, the count of the original list is the amount of unique anagrams a string contains.

            private static List<string> anagrams = new List<string>();
    
            static void Main(string[] args)
            {
                string str = "AAAB";
    
                char[] charArry = str.ToCharArray();
                Permute(charArry, 0, str.Count() - 1);
    
                List<string> copyList = new List<string>();
    
                for(int i = 0; i < anagrams.Count - 1; i++)
                {
                    List<string> anagramSublist = anagrams.GetRange(i + 1, anagrams.Count - 1 - i);
                    var perm = anagrams.ElementAt(i);
    
                    if (anagramSublist.Contains(perm))
                    {
                        copyList.Add(perm);
                    }
                }
    
                foreach(var copy in copyList)
                {
                    anagrams.Remove(copy);
                }
    
                Console.WriteLine(anagrams.Count);
                Console.ReadKey();
            }
    
            static void Permute(char[] arry, int i, int n)
            {
                int j;
                if (i == n)
                {
                    var temp = string.Empty;
                    foreach(var character in arry)
                    {
                        temp += character;
                    }
                    anagrams.Add(temp);
                }
                    
                else
                {
                    for (j = i; j <= n; j++)
                    {
                        Swap(ref arry[i], ref arry[j]);
                        Permute(arry, i + 1, n);
                        Swap(ref arry[i], ref arry[j]); //backtrack
                    }
                }
            }
    
            static void Swap(ref char a, ref char b)
            {
                char tmp;
                tmp = a;
                a = b;
                b = tmp;
            }
    

    Final Notes

    I know this isn't the cleanest, nor best solution. This is simply one that carries the best across the 3 object oriented languages I know, that's also not too complex of a solution. Simple to understand, simple to change languages, so it's the answer I've decided to give.

    EDIT

    Here's the a new answer based on the comments of this answer.

            static void Main(string[] args)
            {
                var str = "abaa";
                var strAsArray = new string(str.ToCharArray());
                var duplicateCount = 0;
                List<char> dupedCharacters = new List<char>();
    
                foreach(var character in strAsArray)
                {
                    if(str.Count(f => (f == character)) > 1 && !dupedCharacters.Contains(character))
                    {
                        duplicateCount += str.Count(f => (f == character));
                        dupedCharacters.Add(character);
                    }
                }
                
                Console.WriteLine("The number of possible anagrams is: " + (factorial(str.Count()) / factorial(duplicateCount)));
                Console.ReadLine();
    
                int factorial(int num)
                {
                    if(num <= 1)
                        return 1;
    
                    return num * factorial(num - 1);
                }
            }