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>

1 comment:

Divye Kapoor said...

Nice use of generators in C#. I have to see if such a construct can be emulated in C++.