Add method to get all permutations (TheAlgorithms#293)

ashotjanibekyan · web-flow · commit 874422c6e43c · 2022-02-24T22:31:35.000+02:00
diff --git a/Algorithms.Tests/Strings/PermutationTests.cs b/Algorithms.Tests/Strings/PermutationTests.cs
@@ -0,0 +1,75 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using Algorithms.Numeric;
+using Algorithms.Strings;
+using FluentAssertions;
+using NUnit.Framework;
+
+namespace Algorithms.Tests.Strings
+{
+    public class PermutationTests
+    {
+        [TestCase("")]
+        [TestCase("A")]
+        [TestCase("abcd")]
+        [TestCase("aabcd")]
+        [TestCase("aabbbcd")]
+        [TestCase("aabbbccccd")]
+        public void Test_GetEveryUniquePermutation(string word)
+        {
+            var permutations = Permutation.GetEveryUniquePermutation(word);
+
+            // We need to make sure that
+            // 1. We have the right number of permutations
+            // 2. Every string in permutations List is a permutation of word
+            // 3. There are no repetitions
+
+            // Start 1.
+            // The number of unique permutations is
+            // n!/(A1! * A2! * ... An!)
+            // where n is the length of word and Ai is the number of occurrences if ith char in the string
+            var charOccurrence = new Dictionary<char, int>();
+            foreach (var c in word)
+            {
+                if (charOccurrence.ContainsKey(c))
+                {
+                    charOccurrence[c] += 1;
+                }
+                else
+                {
+                    charOccurrence[c] = 1;
+                }
+            }
+            // now we know the values of A1, A2, ..., An
+            // evaluate the above formula
+            var expectedNumberOfAnagrams = Factorial.Calculate(word.Length);
+            expectedNumberOfAnagrams = charOccurrence.Aggregate(expectedNumberOfAnagrams, (current, keyValuePair) =>
+            {
+                return current / Factorial.Calculate(keyValuePair.Value);
+            });
+            Assert.AreEqual(expectedNumberOfAnagrams, permutations.Count);
+            // End 1.
+
+            // Start 2
+            // string A is a permutation of string B if and only if sorted(A) == sorted(b)
+            var wordSorted = SortString(word);
+            foreach (var permutation in permutations)
+            {
+                Assert.AreEqual(wordSorted, SortString(permutation));
+            }
+            // End 2
+
+            // Start 3
+            Assert.AreEqual(permutations.Count, new HashSet<string>(permutations).Count);
+            // End 3
+        }
+
+        private static string SortString(string word)
+        {
+            var asArray = word.ToArray();
+            Array.Sort(asArray);
+            return new string(asArray);
+        }
+    }
+}
diff --git a/Algorithms/Strings/Palindrome.cs b/Algorithms/Strings/Palindrome.cs
diff --git a/Algorithms/Strings/Permutation.cs b/Algorithms/Strings/Permutation.cs
@@ -0,0 +1,34 @@
+﻿using System.Collections.Generic;
+using System.Linq;
+
+namespace Algorithms.Strings
+{
+    public static class Permutation
+    {
+        /// <summary>
+        /// Returns every anagram of a given word.
+        /// </summary>
+        /// <returns>List of anagrams.</returns>
+        public static List<string> GetEveryUniquePermutation(string word)
+        {
+            if (word.Length < 2)
+            {
+                return new List<string>
+                {
+                    word,
+                };
+            }
+
+            var result = new HashSet<string>();
+
+            for (var i = 0; i < word.Length; i++)
+            {
+                var temp = GetEveryUniquePermutation(word.Remove(i, 1));
+
+                result.UnionWith(temp.Select(subPerm => word[i] + subPerm));
+            }
+
+            return result.ToList();
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -122,6 +122,7 @@ This repository contains algorithms and data structures implemented in C# for ed
     * [Rabin Karp](./Algorithms/Strings/RabinKarp.cs)
     * [Boyer Moore](./Algorithms/Strings/BoyerMoore.cs)
     * [Palindrome Checker](./Algorithms/Strings/palindrome.cs)
+    * [Get all permutations of a string](./Algorithms/Strings/Permutation.cs)
   * [Other](./Algorithms/Other)
     * [Fermat Prime Checker](./Algorithms/Other/FermatPrimeChecker.cs)
     * [Sieve of Eratosthenes](./Algorithms/Other/SieveOfEratosthenes.cs)
