## Thursday, October 9, 2008

### Permutations and Anagrams

I needed to generate some anagrams, which I know falls into the area Permutations (combinations being altogether the wrong thing for this). There is a nice code sample on Wikipedia that shows how to generate these for an unordered collection.

I implemented a generic class to carry out permutations for me, I changed it to be based on an iterator pattern as often you don't want to generate the whole set, mainly because of the big-oh O(n!), class is therefore:

`class Permutation<T>{  IEnumerable<T> set;  private Permutation()  {  }  public Permutation(IEnumerable<T> set)  {    this.set = set;  }  public IEnumerable<IEnumerable<T>> Mutations  {    get    {      int length = set.Count();      int factorialK = (int)Factorial(length);      for (int k = 0; k < factorialK; k++)        yield return GeneratePermutation(k, set, length);    }  }  private static IEnumerable<T> GeneratePermutation(long k, IEnumerable<T> set, int length)  {    T[] result = set.ToArray();    for (int j = 2; j <= length; j++)    {      k = k / (j - 1);      int dest = (int)(k % j);      int source = j - 1;      if (source != dest)        Swap(ref result[dest], ref result[source]);    }    return result;  }  private static void Swap(ref T a, ref T b)  {    T temp = a;    a = b;    b = temp;  }  private static long Factorial(int n)  {    long result = 1L;    for (int integer = 2; integer <= n; integer++)      result *= integer;    return result;  }}`

which allowed me to write the following code to generate ananagrams:

`static void Main(string[] args){  string word = "ape";  List<string> anagrams = GenerateAnagrams(word);  anagrams.Sort();  Console.WriteLine("{0} anagrams", anagrams.Count);  anagrams.ForEach(anagram => Console.WriteLine(anagram));}private static List<string> GenerateAnagrams(string word){  List<string> sets = new List<string>();  Permutation<char> perm = new Permutation<char>(word);  foreach (char[] combo in perm.Mutations)    sets.Add(combo.ToString());  return sets;}`

note that we are taking advantage of string being a char[], for other types such as int would need to be passed as an array, list or similar IEnumerable<T>