15,792,870 members
Articles / Programming Languages / C#

# Really Simple Anagram Solver

Rate me:
9 Sep 2011CPOL1 min read 35.5K   662   6   5
One really simple anagram solver using recursion.

## Introduction

I will be back! This is my first post since 5 years ago! If you have been interviewed by Microsoft before, you might have come across this kind of recursive questions. I have written a few different solutions, and this is so far my latest, and maybe the smallest one.

## Background

Always good to get your mind juggled a little bit. If you are in the middle of a Tech Access for a job, hope it can help and good luck!

## Using the Code

If you have VS2010, you will know how to run this project. Here is the recursive method:

C#
```static void GenerateAnagram(IList<string> result, string prefix, string src)
{
if (src.Length == 0)
{
return;
}

for (int i = 0; i < src.Length; i++ )
{
string tempPrefix = src[i].ToString();
string newSrc = src.Substring(0, i) + src.Substring(i + 1);
var temp = new List<string>();
GenerateAnagram(temp, tempPrefix, newSrc);
foreach (var s in temp)
{
}
}
}```

And here is how to call it:

C#
```var result = new List<string>();
GenerateAnagram(result, "", "ABC");```

And after one of my reader pointed out the memory problem, here is another approach using recursion:

C#
```static IEnumerable<string> GenerateAnagramAlt(string src)
{
if (src.Length == 0) yield break;
if (src.Length == 1) yield return src;

foreach (string rest in GenerateAnagramAlt(src.Substring(1)))
{
for (int i = 0; i < src.Length; i++)
{
string temp = rest.Substring(0, i) + src[0] + rest.Substring(i);
yield return temp;
}
}
}```

I prefer this one as it doesn't have the memory limitation and nearly twice faster when n >= 9 characters. I like its `IEnumberable` syntax as well! I have updated a new project to include the source file. Thanks goes to my friend ajasin1, who came up with this.

## Points of Interest

I have not included logic to filter duplicated cases, as it can be done using LINQ quite easily.

## History

• 08-09-2011: First posted.
• 09-09-2011: 2.0 posted for `GenerateAnagramAlt`.

Written By
Software Developer (Senior) www.wonga.com
Ireland
I have over 13 Years IT industry experience as Principle/Senior Programmer. I am experienced in .NET/J2EE system design and detailed implementation. I master UML modelling and OO design methodology with a strong C#/C++/Java coding background. I have been in working/managing a distributed project using Agile/Waterfall approach. My business knowledge includes Telecommunication, Financial Investment/Trading, and Banking.

 First Prev Next
 My vote of 2 BitcoinTycoon13-Sep-11 8:30 BitcoinTycoon 13-Sep-11 8:30
 Quickly Out of Memory GenJerDan8-Sep-11 7:05 GenJerDan 8-Sep-11 7:05
 Re: Quickly Out of Memory Ziming8-Sep-11 10:00 Ziming 8-Sep-11 10:00
 Re: Quickly Out of Memory GenJerDan8-Sep-11 10:07 GenJerDan 8-Sep-11 10:07
 Re: Quickly Out of Memory Ziming8-Sep-11 11:03 Ziming 8-Sep-11 11:03
 This reminded me the old tale about the wise man and king, that on one chess board could hold all the grains on earth. Yes, it's impossible to hold all anagram in memory! There has to be a way to filter them upon generation or located out of memory. Simple is the best.
 Last Visit: 31-Dec-99 19:00     Last Update: 2-Dec-23 5:53 Refresh 1